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

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

Концепция

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

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

Алгоритм

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

(1) Проверьте, меньше ли одно из простых чисел или равно наименьшему из двух значений.

B

и

{\sqrt {n}}

делит

n

. Если да, то стоп:

n

составное.

(2) Проверьте,

{\sqrt {n}}\in \mathbb {Z}

. Если да, то стоп:

n

составное.

(3) Вычислить

x^{n+1 \over 2}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)

. Если

x^{n+1 \over 2}\notin \mathbb {Z} {\big /}n\mathbb {Z}

, затем остановитесь:

n

составное.

(4) Вычислить

x^{n+1}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)

. Если

x^{n+1}\not \equiv -c

, затем остановитесь:

n

составное.

(5) Пусть

n^{2}-1=2^{r}s

со

странным

. Если

x^{s}\not \equiv 1{\bmod {\,}}{\big (}n,x^{2}-bx-c)

, и

x^{2^{j}s}\not \equiv -1{\bmod {\,}}{\big (}n,x^{2}-bx-c)

для всех

0\leq j\leq r-2

, затем остановитесь:

n

составное.

Если КТП не останавливается на шагах (1)–(5), то $n$ — вероятное простое число.

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

См. также

Ссылки

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

[Grantham-1] Грэнтэм, Дж. (1998). «Вероятный основной тест с высокой достоверностью». Журнал теории чисел . 72 (1): 32–47. CiteSeerX 10.1.1.56.8827 . дои : 10.1006/jnth.1998.2247 . S2CID 119640473 .

[DamFran-2] Дамгорд, Иван Бьерре ; Франдсен, Гудмунд Сковбьерг (2003). «Расширенный квадратичный тест на простоту Фробениуса с оценками ошибок среднего и наихудшего случая». Основы теории вычислений (PDF) . Конспекты лекций по информатике. Том. 2751. Шпрингер Берлин Гейдельберг. стр. 118–131. дои : 10.1007/978-3-540-45077-1_12 . ISBN 978-3-540-45077-1 . ISSN 1611-3349 .

[1]

[2]

v т и Теоретико-числовые алгоритмы
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms