Квадратичный тест Фробениуса

Квадратичный тест Фробениуса ( QFT ) является вероятностным тестом простоты чисел для испытания ряда , является ли вероятным премьером . Он назван в честь Фердинанда Георга Фробениуса . В тесте используются понятия квадратичных многочленов и автоморфизма Фробениуса . Его не следует путать с более общим тестом Фробениуса, использующим квадратичный многочлен - QFT ограничивает допустимые многочлены на основе входных данных, а также имеет другие условия, которые должны быть выполнены. Композит проходит этот тест является псевдопростое число Фробениуса , но обратное не всегда верно.

Концепция [ править ]

Заявленная цель Грэнтэма при разработке алгоритма состояла в том, чтобы предоставить тест, который всегда будет проходить простые числа, а композиты - с вероятностью менее 1/7710. ^{[1] : 33}

Позже Дамгард и Франдсен расширили этот тест до теста, называемого расширенным квадратичным тестом Фробениуса (EQFT). ^[2]

Алгоритм [ править ]

Пусть n - натуральное число, такое что n нечетно, и , где обозначает символ Якоби . Установить . Тогда QFT на n с параметрами ( b , c ) работает следующим образом:${\ displaystyle \ left ({\ frac {b ^ {2} + 4c} {n}} \ right) = - 1}$${\displaystyle \left({\frac {-c}{n}}\right)=1}$${\displaystyle \left({\frac {x}{n}}\right)}$${\displaystyle B=50000}$

(1) Проверьте, является ли одно из простых чисел меньшим или равным меньшему из двух значений и делит ли n . Если да, то остановитесь, поскольку n составное.${\displaystyle B}$${\displaystyle {\sqrt {n}}}$

(2) Проверьте, действительно ли . Если да, то остановитесь, поскольку n составное.${\displaystyle {\sqrt {n}}\in \mathbb {Z} }$

(3) Вычислить . Если тогда остановитесь, поскольку n составное.${\displaystyle x^{n+1 \over 2}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$${\displaystyle x^{n+1 \over 2}\notin \mathbb {Z} {\big /}n\mathbb {Z} }$

(4) Вычислить . Если тогда остановитесь, поскольку n составное.${\displaystyle x^{n+1}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$${\displaystyle x^{n+1}\not \equiv -c}$

(5) Пусть с нечетным s . Если и для всех , то остановитесь, поскольку n составное.${\displaystyle n^{2}-1=2^{r}s}$${\displaystyle x^{s}\not \equiv 1{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$${\displaystyle x^{2^{j}s}\not \equiv -1{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$${\displaystyle 0\leq j\leq r-2}$

Если QFT не останавливается на шагах (1) - (5), то n - вероятное простое число.

(Обозначение означает, что , где H и K - многочлены.)${\displaystyle A\equiv B{\bmod {\,}}(n,\,f(x))}$${\displaystyle A-B=H(x)\cdot n+K(x)\cdot f(x)}$

См. Также [ править ]

• Целые числа по модулю n
• Мультипликативная группа целых чисел по модулю n

Ссылки [ править ]