Тест на простоту AKS - AKS primality test

Тест простоты AKS (также известный как тест простоты Агравала – Каяла – Саксены и циклотомический тест AKS ) - это детерминированный алгоритм доказательства простоты , созданный и опубликованный Маниндрой Агравал , Нираджем Каялом и Нитином Саксеной , компьютерными учеными из Индийского технологического института Канпура. , 6 августа 2002 г., в статье "ПРИМЕРЫ в П". Алгоритм был первым, который может доказуемо определить, является ли данное число простым или составным за полиномиальное время , не полагаясь на математические гипотезы, такие как обобщенная гипотеза Римана . Доказательство также примечательно тем, что не опирается на область анализа . В 2006 году авторы получили как гёделевскую премию и Фулкерсон премию за свою работу.

Важность

AKS - это первый алгоритм доказательства простоты, который одновременно является общим , полиномиальным , детерминированным и безусловным . Предыдущие алгоритмы разрабатывались веками и достигли максимум трех из этих свойств, но не всех четырех.

Алгоритм AKS может использоваться для проверки простоты любого заданного общего числа. Известно множество быстрых тестов на простоту, которые работают только для чисел с определенными свойствами. Например, тест Лукаса – Лемера работает только для чисел Мерсенна , в то время как тест Пепена применим только к числам Ферма .
Максимальное время работы алгоритма может быть выражено как полином по количеству цифр в целевом числе. ECPP и APR окончательно доказывают или опровергают, что данное число является простым, но не известно, что они имеют полиномиальные временные границы для всех входных данных.
Гарантируется, что алгоритм детерминированно распознает, является ли целевое число простым или составным. Рандомизированные тесты, такие как Миллера – Рабина и Бэйли – PSW , могут проверять простоту любого заданного числа за полиномиальное время, но, как известно, дают только вероятностный результат.
Правильность AKS не зависит от какой-либо дополнительной недоказанной гипотезы . Напротив, версия Миллера-Рабина полностью детерминирована и выполняется за полиномиальное время по всем входным параметрам, но ее правильность зависит от истинности еще не доказанной обобщенной гипотезы Римана .

Хотя алгоритм имеет огромное теоретическое значение, он не используется на практике, что делает его галактическим алгоритмом . Для 64-битных входных данных тест простоты Baillie – PSW является детерминированным и выполняется на много порядков быстрее. Для больших входных данных производительность (также безусловно правильных) тестов ECPP и APR намного превосходит AKS. Кроме того, ECPP может выводить сертификат первичности, который позволяет независимую и быструю проверку результатов, что невозможно с алгоритмом AKS.

Концепции

Тест на простоту AKS основан на следующей теореме: если задано целое и целое число, взаимно простое с , является простым тогда и только тогда, когда соотношение полиномиальной конгруэнтности ${\ Displaystyle п \ geq 2}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle n}$

{\ Displaystyle (Х + а) ^ {п} \ эквив Х ^ {п} + а {\ pmod {п}}}

( 1 )

внутри кольца многочленов . Обратите внимание, что это означает неопределенное, которое порождает это кольцо многочленов. ${\ Displaystyle \ mathbb {Z} _ {п} [X]}$ ${\ displaystyle X}$

Эта теорема является обобщением малой теоремы Ферма на многочлены . В одном направлении это можно легко доказать, используя биномиальную теорему вместе со следующим свойством биномиального коэффициента :

{\ Displaystyle {п \ выбрать k} \ эквив 0 {\ pmod {п}}}

для всех, если прост.

{\ Displaystyle 0 <к <п}

{\ displaystyle n}

Хотя соотношение ( 1 ) само по себе представляет собой тест на простоту, проверка его занимает экспоненциальное время : метод грубой силы потребует расширения полинома и уменьшения результирующих коэффициентов. ${\ Displaystyle (Х + а) ^ {п}}$ ${\ Displaystyle {\ pmod {п}}}$ ${\ displaystyle n + 1}$

Сравнение есть равенство в кольце многочленов . Вычисление в кольце частных создает верхнюю границу степени задействованных многочленов. AKS оценивает равенство в , делая вычислительную сложность зависимой от размера . Для наглядности это выражается как соответствие ${\ Displaystyle \ mathbb {Z} _ {п} [X]}$ ${\ Displaystyle \ mathbb {Z} _ {п} [X]}$ ${\ Displaystyle \ mathbb {Z} _ {п} [X] / (X ^ {r} -1)}$ ${\ displaystyle r}$

{\ Displaystyle (Х + а) ^ {п} \ эквив (Х ^ {п} + а) {\ pmod {X ^ {г} -1, п}}}

( 2 )

что то же самое, что:

{\ displaystyle (X + a) ^ {n} - (X ^ {n} + a) = (X ^ {r} -1) g + nf}

( 3 )

для некоторых полиномов и . ${\ displaystyle f}$ ${\ displaystyle g}$

Обратите внимание, что все простые числа удовлетворяют этому соотношению (выбор в ( 3 ) дает ( 1 ), которое справедливо для простых чисел ). Это сравнение можно проверить за полиномиальное время, если оно полиномиально от цифр . Алгоритм AKS оценивает это соответствие для большого набора значений, размер которых полиномиален цифрам . Доказательство достоверности алгоритма AKS показывает, что можно найти и набор значений с указанными выше свойствами, так что если сравнения выполняются, то является степенью простого числа. ${\ displaystyle g = 0}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle a}$ ${\ displaystyle n}$

История и время работы

В первой версии процитированной выше статьи авторы доказали, что асимптотическая временная сложность алгоритма равна (используя Õ из нотации большого O ) - двенадцатую степень числа цифр в n раз, множитель, который является полилогарифмическим в количество цифр. Однако эта верхняя граница была довольно нечеткой; широко распространенная гипотеза о распределении простых чисел Софи Жермен , если она верна, немедленно сократила бы худший случай до . ${\ Displaystyle {\ тильда {O}} (\ log (п) ^ {12})}$ ${\ Displaystyle {\ тильда {O}} (\ журнал (п) ^ {6})}$

Через несколько месяцев после открытия появились новые варианты (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a / b, Lenstra and Pomerance 2003), которые значительно повысили скорость вычислений. Из-за существования множества вариантов Крэндалл и Пападопулос ссылаются на «класс алгоритмов AKS» в своей научной статье «О реализации тестов на простоту класса AKS», опубликованной в марте 2003 года.

В ответ на некоторые из этих вариантов, а также на другие отзывы, статья «PRIMES is in P» была обновлена новой формулировкой алгоритма AKS и доказательства его правильности. (Эта версия в конечном итоге была опубликована в Annals of Mathematics .) Хотя основная идея осталась прежней, r был выбран новым способом, и доказательство правильности было организовано более последовательно. Новое доказательство основывалось почти исключительно на поведении круговых многочленов над конечными полями . Новая верхняя граница временной сложности была позже уменьшена с использованием дополнительных результатов теории решет до . ${\ Displaystyle {\ тильда {O}} (\ log (п) ^ {10.5})}$ ${\ Displaystyle {\ тильда {O}} (\ log (п) ^ {7.5})}$

В 2005 году Померанс и Ленстра продемонстрировали вариант AKS, который работает в рабочем состоянии, что привело к созданию еще одной обновленной версии документа. Агравал, Каял и Саксена предложили вариант, который работал бы, если бы гипотеза Агравала была верна; однако эвристический аргумент Померанса и Ленстры показал, что он, вероятно, неверен. ${\ Displaystyle {\ тильда {O}} (\ журнал (п) ^ {6})}$ ${\ Displaystyle {\ тильда {O}} (\ журнал (п) ^ {3})}$

Алгоритм

Алгоритм следующий:

Ввод: целое число

n > 1

.

Проверьте , если п является идеальной мощность : если $п = б$ для целых чисел $через > 1$ и $Ь > 1$ , выходной композитного .
Найдите наименьшее r такое, что $ord r (n)> (log 2 n) 2$ . (если r и n не взаимно просты, пропустите это r )
Для всех 2 ≤ a ≤ min ( r , n −1) проверьте, что a не делит n : если a | n для некоторого 2 ≤ a ≤ min ( r , n −1), выходной составной .
Если n ≤ r , вывести простое число .
Для $a = 1$ нужно сделать ${\ displaystyle \ left \ lfloor {\ sqrt {\ varphi (r)}} \ log _ {2} (n) \ right \ rfloor}$
если ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r - 1, n ), вывести составной ;
Вывести простое число .

Здесь Ord _г ( п ) является мультипликативным порядком из п по модулю г , бревенчатый ₂ представляет собой двоичный логарифм , и это totient функция Эйлера из г . ${\ displaystyle \ varphi (r)}$

Шаг 3 показан в документе как проверка 1 <( a , n ) < n для всех a ≤ r . Видно, что это эквивалентно пробному делению до r , которое может быть выполнено очень эффективно без использования gcd . Точно так же сравнение на шаге 4 может быть заменено на то, чтобы пробное деление возвращало простое число после проверки всех значений до включительно ${\ displaystyle \ left \ lfloor {\ sqrt {n}} \ right \ rfloor.}$

Выйдя за пределы очень маленьких входов, шаг 5 доминирует над затраченным временем. Существенное снижение сложности (от экспоненциальной к полиномиальной) достигается выполнением всех вычислений в конечном кольце

{\ Displaystyle R: = {\ Bigl (} {\ bigl (} \ mathbb {Z} / (n) {\ bigr)} [X] {\ Bigr)} {\ Bigl /} (X ^ {r} \ ! \! - \! \! 1) {\ Bigr.}}

состоящий из элементов. Это кольцо содержит только одночлены , а коэффициенты , в которых есть элементы, все они кодируются в битах. ${\ displaystyle n \ cdot r}$ ${\ displaystyle r}$ ${\ displaystyle \ {X ^ {0}, X ^ {1}, \ ldots, X ^ {r-1} \}}$ ${\ Displaystyle \ mathbb {Z} / (п) =: \ mathbb {Z} _ {п}}$ ${\ displaystyle n}$ ${\ Displaystyle \ журнал _ {2} (п)}$

Большинство более поздних улучшений, внесенных в алгоритм, были сосредоточены на уменьшении размера r, что ускоряет выполнение основной операции на шаге 5, и на уменьшении размера s , количества циклов, выполняемых на шаге 5. Обычно эти изменения не меняют вычислений. сложность, но может привести к тому, что потребуется на много порядков меньше времени, например, окончательная версия Бернштейна имеет теоретическое ускорение более чем в 2 миллиона раз.

Схема доказательства действительности

Чтобы алгоритм был правильным, все шаги, которые определяют n, должны быть правильными. Шаги 1, 3 и 4 тривиально верны, поскольку они основаны на прямых проверках делимости n . Шаг 5 тоже верно: так как (2) справедливо при любом выборе в копервичных к п и г , если п простое, неравенство означает , что п должно быть составным.

Сложным случаем алгоритма является повторение оператора на шаге 5. Если это в пределах конечного кольца R, происходит несовпадение

{\ Displaystyle и \ не \ Equiv v \; {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1), п {\ bigr)}}

это эквивалентно

{\ Displaystyle и \ эквив v \; {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1) {\ bigr)} \ quad \ подразумевает \ quad u \ not \ Equiv v \; ({\ text {mod}} n)}

,

так что после сокращения до r мономов с помощью только нужно проверять. ${\ displaystyle {\ text {mod}} (X ^ {r} \! \! - \! \! 1)}$ ${\ Displaystyle и \ не \ эквив v \; ({\ текст {mod}} п)}$

Пример 1: n = 31 простое число

Ввод: целое число n = 31> 1.

  If n = a^b for integers a > 1 and b > 1, output composite.
    For [ b=2, b <= log₂(n), b++,
      a=n^1/b;
      If [ a is integer, Return[Composite]]
    ];
    a=n^1/2...n^1/4={5.568, 3.141, 2.360}

  Find the smallest r such that O_r(n) > (log₂ n)².
    maxk=⌊(log₂ n)²⌋;
    maxr=Max[3, ⌈(Log₂ n)⁵⌉]; (*maxr really isn't needed*)
    nextR=True;
    For [r=2, nextR && r < maxr, r++,
      nextR=False;
      For [k=1,(!nextR) &&k ≤ maxk, k++,
        nextR=(Mod[n^k, r]==1 || Mod[n^k, r]==0)
      ]
    ];
    r--; (*the loop over increments by one*)
     
    r = 29

  If 1 < gcd(a,n) < n for some a ≤ r, output composite.
    For [a=r, a > 1, a--,
      If [(gcd=GCD[a,n]) > 1 && gcd < n, Return[Composite]]
    ];
     
    gcd={GCD(29,31)=1, GCD(28,31)=1, ..., GCD(2,31)=1} ≯ 1

  If n ≤ r, output prime.
    If [n ≤ r, Return[Prime]]; (* this step may be omitted if n > 5690034 *)
     
    31 > 29

  For a = 1 to  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$  do
    if (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), output composite;
     
    φ[x_]:=EulerPhi[x];
    PolyModulo[f_]:=PolynomialMod[ PolynomialRemainder[f,x^r-1,x],n];
    max=Floor[Log[2,n]√φ[r]];
    For[a=1, a ≤ max, a++,
      If[PolyModulo[(x+a)ⁿ-PolynomialRemainder[xⁿ+a, x^r-1], x]≠0,
        Return[Composite]
      ]
    ];
     
    (x+a)³¹ =
      a³¹ +31a³⁰x +465a²⁹x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸ +465a²x²⁹ +31ax³⁰ +x³¹
     
    PolynomialRemainder [(x+a)³¹, x²⁹-1] =
      465a² +a³¹ +(31a+31a³⁰)x +(1+465a²⁹)x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸
     
    (A) PolynomialMod [PolynomialRemainder [(x+a)³¹, x²⁹-1], 31] = a³¹+x²
     
    (B) PolynomialRemainder [x³¹+a, x²⁹-1] = a+x²
     
    (A) - (B) = a³¹+x² - (a+x²) = a³¹-a
     
    max =  $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$  = 26
     
    {1³¹-1=0 (mod 31), 2³¹-2=0 (mod 31), 3³¹-3=0 (mod 31), ..., 26³¹-26=0 (mod 31)}

```
  Output prime.
    31 Must be Prime
```

Где PolynomialMod - это почленное сокращение полинома по модулю. например, PolynomialMod [x + 2x ² + 3x ³ , 3] = x + 2x ² + 0x ³

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

дальнейшее чтение

Дицфельбингер, Мартин (2004). Проверка на простоту за полиномиальное время. Из рандомизированных алгоритмов к PRIMES в P . Конспект лекций по информатике. 3000 . Берлин: Springer-Verlag . ISBN 3-540-40344-2. Zbl 1058.11070 .

внешние ссылки

Вайсштейн, Эрик В. «Тест на простоту AKS» . MathWorld .
Р. Крэндалл, Apple ACG и Дж. Пападопулос (18 марта 2003 г.): О реализации тестов простоты класса AKS (PDF)
Статья Борнемана, содержащая фотографии и информацию о трех индийских ученых (PDF)
Эндрю Гранвилл: Легко определить, является ли данное целое число простым.
Основные факты: от Евклида до AKS , Скотт Ааронсон (PDF)
PRIMES находится в P маленьком FAQ от Антона Стиглика.
Присуждение премии Гёделя за 2006 год
Присуждение премии Фулкерсона за 2006 год
Ресурс алгоритма AKS "PRIMES in P"
Грайм, доктор Джеймс. «Тест на защиту от дурака для простых чисел - Numberphile» (видео) . Брэди Харан . [видео описывает экспоненциальную зависимость времени (1), которую он называет AKS]

Languages

In other projects