Тест простоты AKS

Алгоритм проверки простых чисел

Тест на простоту AKS (также известный как тест на простоту Агравала–Каяла–Саксены и циклотомический тест AKS ) — это детерминированный алгоритм доказательства простоты, созданный и опубликованный Маниндрой Агравалом , Нираджем Каялом и Нитином Саксеной , специалистами по информатике из Индийского технологического института в Канпуре , 6 августа 2002 года в статье под названием «PRIMES is in P». ^[1] Этот алгоритм был первым, который способен за полиномиальное время определить , является ли заданное число простым или составным , и это без опоры на математические гипотезы, такие как обобщенная гипотеза Римана . Доказательство также примечательно тем, что не опирается на область анализа . ^[2] В 2006 году авторы получили за свою работу как премию Гёделя , так и премию Фулкерсона .

Важность

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

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

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

Концепции

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

выполняется внутри кольца многочленов . ^[1] Обратите внимание, что обозначает неопределенность , которая порождает это кольцо многочленов. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$ ${\displaystyle X}$

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

${\displaystyle {n \choose k}\equiv 0{\pmod {n}}}$для всех, если является простым. ${\displaystyle 0<k<n}$ ${\displaystyle n}$

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

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

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

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

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

История и время действия

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

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

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

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

Алгоритм

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

Вход: целое число n  > 1 .

1. Проверьте, является ли n совершенной степенью : если n  =  a ^b для целых чисел a  > 1 и b  > 1 , то выведите составное число .
2. Найдите наименьшее r такое, что ord _r ( n ) > (log ₂ n ) ² . Если r и n не являются взаимно простыми, то выведите составное число .
3. Для всех 2 ≤ a ≤ min ( r , n −1) проверьте, что a не делит n : Если a | n для некоторого 2 ≤ a ≤ min ( r , n −1), то выведите composite .
4. Если n ≤ r , то выведите простое число .
5. Для a =  1 сделать ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$

   если ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r − 1, n ), то вывести составной ;

6. Выходной простой .

Здесь ord _r ( n ) — мультипликативный порядок n по модулю r , log ₂ — двоичный логарифм , а — функция Эйлера от r . ${\displaystyle \varphi (r)}$

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

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

${\displaystyle R=(\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)}$

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

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

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

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

Трудная часть доказательства — показать, что шаг 6 верен. Его доказательство правильности основано на верхней и нижней границах мультипликативной группы , построенной из ( X + a ) двучленов, которые проверяются на шаге 5. Шаг 4 гарантирует, что эти двучлены являются различными элементами . Для конкретного выбора r границы приводят к противоречию, если только n не является простым числом или степенью простого числа. Вместе с проверкой шага 1 это означает, что n всегда является простым числом на шаге 6. ^[1] ${\displaystyle \mathbb {Z} _{n}[x]}$ ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$ ${\displaystyle \mathbb {Z} _{n}[x]}$

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

 Вход : целое число n = 31 > 1. (* Шаг 1 *)  Если ( n = a b для целых чисел a > 1 и b > 1), выведите  составное . Для (b = 2; b <= log 2 (n); b++) { a = n 1/b ; Если (a — целое число), вернуть [Composite] } а = n 1/2 ...n 1/4 = {5,568, 3,141, 2,360} (* Шаг 2 *) Найдите наименьшее r такое, что O r ( n ) > (log 2  n ) 2 . макск = ⌊(log 2 n) 2 ⌋; maxr = Max[3, ⌈(Log 2 n) 5 ⌉]; (* maxr на самом деле не нужен *) следующийR = Истина; Для (r = 2; nextR && r < maxr; r++) { следующийR = Ложь; For (k = 1; (!nextR) && k ≤ maxk; k++) { следующийR = (Mod[n k , r] == 1 || Mod[n k , r]==0) } } r--; (*цикл увеличивается на единицу*)  г = 29 (* Шаг 3 *)  Если (1 < gcd ( a , n ) < n для некоторого a ≤ r ), вывести  составное число . Для (a = r; a > 1; a--) { Если ((gcd = GCD[a,n]) > 1 && gcd < n), Вернуть [Составное число] }  НОД = {НОД(29,31)=1, НОД(28,31)=1, ..., НОД(2,31)=1} ≯ 1 (* Шаг 4 *)  Если ( n ≤ r ), вывести  простое число . Если ( n ≤ r), вернуть [Простое число] (* этот шаг можно пропустить, если n > 5690034 *)  31 > 29   ( * Шаг 5 *) Для  a = 1 выполнить  If (( X + a ) n ≠ X n + a (mod X r − 1, n )), вывести составной ; ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$     φ[x_] := ЭйлерФи[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) n - PolynomialRemainder[x n +a, x r -1], x] ≠ 0) { Return [Composite] { }  (х+а) 31 = а 31 +31а 30 х +465а 29 х 2 +4495а 28 х 3 +31465а 27 х 4 +169911а 26 х 5 +736281а 25 х 6 +2629575а 24 х 7 +7888725а 23 х 8 [phone]а 22 х 9 [phone]а 21 х 10 [phone]а 20 х 11 [phone]а 19 х 12 [phone]а 18 х 13 [phone]а 17 х 14 [phone]а 16 х 15 [phone]а 15 х 16 [phone]a 14 х 17 [phone]a 13 х 18 [phone]a 12 х 19 [phone]a 11 х 20 [phone]a 10 х 21 [phone]a 9 х 22 +7888725a 8 х 23 +2629575a 7 х 24 +736281a 6 х 25 +169911a 5 х 26 +31465a 4 х 27 +4495a 3 х 28 +465a 2 х 29 +31ax 30 +x 31  ПолиномиальныйОстаток [(x+a) 31 , x 29 -1] = 465a 2 +a 31 +(31a+31a 30 )x +(1+465a 29 )x 2 +4495a 28 x 3 +31465a 27 x 4 +169911a 26 x 5 +736281a 25 x 6 +2629575a 24 x 7 +7888725a 23 x 8 [phone]a 22 x 9 [phone]a 21 x 10 [phone]a 20 x 11 [phone]a 19 x 12 [phone]a 18 x 13 [phone]a 17 x 14 [phone]a 16 х 15 [phone]a 15 х 16 [phone]a 14 х 17 [phone]a 13 х 18 [phone]a 12 х 19 [phone]a 11 х 20 [phone]a 10 х 21 [phone]a 9 х 22 +7888725a 8 х 23 +2629575a 7 х 24 +736281a 6 х 25 +169911a 5 х 26 +31465a 4 х 27 +4495a 3 х 28  ( A ) ПолиномиальныйОстаток [ПолиномиальныйОстаток [(x+a) 31 , x 29 -1], 31] = a 31 +x 2  ( B ) ПолиномиальныйОстаток [x 31 +a, x 29 -1] = a+x 2  ( А ) - ( В ) = а 31 + х 2 - (а + х 2 ) = а 31 - а   ${\displaystyle \max =\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor =26}$  {1 31 -1 = 0 (по модулю 31), 2 31 -2 = 0 (по модулю 31), 3 31 -3 = 0 (по модулю 31), ..., 26 31 -26 = 0 (по модулю 31)}  (* Шаг 6 *)  Вывести  простое число . 31 Должно быть простое число

Где PolynomialMod — это почленное уменьшение по модулю полинома. Например, PolynomialMod[x+2x ² +3x ³ , 3] = x+2x ² +0x ³

^[6]

Ссылки

1. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR  3597229.
2. Грэнвилл, Эндрю (2005). «Легко определить, является ли заданное целое число простым». Bull. Amer. Math. Soc . 42 : 3–38. doi : 10.1090/S0273-0979-04-01037-7 .
3. HW Lenstra Jr. и Carl Pomerance, «Проверка простоты с гауссовыми периодами», предварительная версия, 20 июля 2005 г.
4. HW Lenstra Jr. и Carl Pomerance, «Проверка простоты с помощью гауссовых периодов. Архивировано 25 февраля 2012 г. на Wayback Machine », версия от 12 апреля 2011 г.
5. Дэниел Дж. Бернстайн, «Доказательство первичности после Агравала-Каяла-Саксены», версия от 25 января 2003 г.
6. См . страницу обсуждения AKS для обсуждения того, почему отсутствует «Пример 2: n не является простым после шага 4».

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

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

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

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