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

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

Концепция

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

Позже тест был расширен Damgård и Франдсен на тест под названием расширенный квадратичный тест Фробениуса (EQFT).^[2]

Алгоритм

Позволять п - натуральное число такое, что п странно, ${ 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}$. Потом QFT на п с параметрами (б, c) работает следующим образом:

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

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

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

(4) Вычислить ${ Displaystyle х ^ {п + 1} , { bmod {,}} { big (} п, х ^ {2} -bx-c)}$. Если ${ Displaystyle х ^ {п + 1} not Equiv -c}$ тогда остановись как п составной.

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

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

(Обозначение ${ Displaystyle А эквив В { bmod {,}} (п, , е (х))}$ Значит это ${ Displaystyle А-В = ЧАС (Икс) CDOT п + К (х) CDOT F (х)}$, где H и K - многочлены.)

Смотрите также

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

использованная литература