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

В квадратичный тест Фробениуса (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 x^{n+1 \over 2}\notin \mathbb {Z} {\big /}n\mathbb {Z} }$ тогда остановись как п составной.

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

(5) Позволять ${\displaystyle n^{2}-1=2^{r}s}$ с участием 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), тогда п - вероятное простое число.

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

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

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

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

1. Грэнтэм, Дж. (1998). «Вероятный основной тест с высокой степенью уверенности». Журнал теории чисел. 72 (1): 32–47. CiteSeerX  10.1.1.56.8827. Дои:10.1006 / jnth.1998.2247.
2. Дамгард, Иван Бьерре; Франдсен, Гудмунд Сковбьерг (2003). Расширенный квадратичный критерий простоты Фробениуса с оценками средней и наихудшей погрешности (PDF). Конспект лекций по информатике. Основы теории вычислений. 2751. Springer Berlin Heidelberg. С. 118–131. Дои:10.1007/978-3-540-45077-1_12. ISBN  978-3-540-45077-1. ISSN  1611-3349.