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

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

Важность

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

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

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

Концепции

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

${\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {n}}}$

(1)

держит.^[1] Обратите внимание, что ${\displaystyle x}$ следует понимать как формальный символ.

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

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

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

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

${\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,n}}}$

(2)

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

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

(3)

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

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

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

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

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

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

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

Алгоритм

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

Ввод: целое число п > 1.

1. Проверить, если п это идеальная сила: если п = а^б для целых чисел а > 1 и б > 1, выход составной.
2. Найдите самый маленький р такой, что ord_р(п)> (журнал₂ п)². (если р и п не взаимно просты, пропустите это р)
3. Для всех 2 ≤ а ≤ мин (р, п−1), убедитесь, что а не разделяет п: Если а|п для некоторых 2 ≤ а ≤ мин (р, п−1), выход составной.
4. Если п ≤ р, выход премьер.
5. За а = 1 к ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$ делать

   если (Икс+а)^п≠ Икс^п+а (мод Икс^р − 1,п), выход составной;

6. Вывод премьер.

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

Шаг 3 показан в документе как проверка 1 <(а,п) < п для всех а ≤ р. Видно, что это эквивалентно пробному разделению до р, что можно сделать очень эффективно без использования 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} /(n)=:\mathbb {Z} _{n}}$ который имеет ${\displaystyle n}$ элементы, все они кодируются в ${\displaystyle \log _{2}(n)}$ биты.

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

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

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

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

${\displaystyle u\not \equiv v\;{\bigl (}{\text{mod }}(x^{r}\!\!-\!\!1),n{\bigr )}}$

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

${\displaystyle u\equiv v\;{\bigl (}{\text{mod }}(x^{r}\!\!-\!\!1){\bigr )}\quad \implies \quad u\not \equiv v\;({\text{mod }}n)}$,

так что после сведения к р одночлены с помощью ${\displaystyle {\text{mod }}(x^{r}\!\!-\!\!1)}$ Только ${\displaystyle u\not \equiv v\;({\text{mod }}n)}$нужно проверить.^[1]

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

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

1.   Если п = аб для целых чисел а > 1 и б > 1, выход составной. Для [b = 2, b <= log2(n), b ++, a = n1 / б; Если [a - целое число, Return [Composite]]]; а = п1/2... п1/4={5.568, 3.141, 2.360}

2.   Найдите самый маленький р такой, что Ор(п)> (журнал2 п)2. maxk = ⌊ (журнал2 п)2⌋; maxr = Макс [3, ⌈ (Журнал2 п)5⌉]; (* maxr действительно не нужен *) nextR = True; Для [r = 2, nextR && r k, r] == 1 || Мод [nk, r] == 0)]]; р--; (* цикл увеличивается на единицу *) r = 29

3.   Если 1 <gcd (а,п) < п для некоторых а ≤ р, выход составной. Для [a = r, a> 1, a--, If [(gcd = GCD [a, n])> 1 && gcd 

4.   Если п ≤ р, выход премьер. Если [n ≤ r, вернуть [Prime]]; (* этот шаг можно пропустить, если n> 5690034 *) 31> 29

5.   За а = От 1 до ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$ делать если (Икс+а)п≠ Иксп+а (мод Икср − 1,п), выход составной; φ [x _]: = ЭйлерФи [x]; PolyModulo [f _]: = PolynomialMod [ Полиномиальный остаток [f, xр-1, x], n]; max = Этаж [Бревно [2, n]√φ [r]]; Для [a = 1, a ≤ max, a ++, If [PolyModulo [(x + a)п-PolynomialRemainder [xп+ а, хр-1], x] ≠ 0, возврат [составной]]]; (х + а)31 = а31 + 31а30х + 465a29Икс2 + 4495a28Икс3 + 31465a27Икс4 + 169911a26Икс5 + 736281a25Икс6 + 2629575a24Икс7 + 7888725a23Икс8 + 20160075a22Икс9 + 44352165a21Икс10 + 84672315a20Икс11 + 141120525a19Икс12 + 206253075a18Икс13 + 265182525a17Икс14 + 300540195a16Икс15 + 300540195a15Икс16 + 265182525a14Икс17 + 206253075a13Икс18 + 141120525a12Икс19 + 84672315a11Икс20 + 44352165a10Икс21 + 20160075a9Икс22 + 7888725a8Икс23 + 2629575a7Икс24 + 736281a6Икс25 + 169911a5Икс26 + 31465a4Икс27 + 4495a3Икс28 + 465a2Икс29 + 31ax30 + х31         PolynomialRemainder [(x + a)31, Икс29-1] = 465a2 + а31 + (31a + 31a30) х + (1 + 465a29)Икс2 + 4495a28Икс3 + 31465a27Икс4 + 169911a26Икс5 + 736281a25Икс6 + 2629575a24Икс7 + 7888725a23Икс8 + 20160075a22Икс9 + 44352165a21Икс10 + 84672315a20Икс11 + 141120525a19Икс12 + 206253075a18Икс13 + 265182525a17Икс14 + 300540195a16Икс15 + 300540195a15Икс16 + 265182525a14Икс17 + 206253075a13Икс18 + 141120525a12Икс19 + 84672315a11Икс20 + 44352165a10Икс21 + 20160075a9Икс22 + 7888725a8Икс23 + 2629575a7Икс24 + 736281a6Икс25 + 169911a5Икс26 + 31465a4Икс27 + 4495a3Икс28         (А) PolynomialMod [PolynomialRemainder [(x + a)31, Икс29-1], 31] = а31+ х2         (B) PolynomialRemainder [x31+ а, х29-1] = а + х2         (А) - (B) = а31+ х2 - (а + х2) = а31-a max =${\displaystyle \left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor }$ = 26         {131-1 = 0 (мод 31), 231-2 = 0 (мод 31), 331-3 = 0 (модуль 31), ..., 2631-26 = 0 (мод 31)}

6.   Вывод премьер. 31 Должно быть Prime

Где 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). «Легко определить, является ли данное целое число простым». Бык. Амер. Математика. Soc. 42: 3–38. Дои:10.1090 / S0273-0979-04-01037-7.
3. Х. В. Ленстра-младший и Карл Померанс "Проверка на простоту с гауссовыми периодами ", предварительная версия от 20 июля 2005 г.
4. Х. В. Ленстра мл. и Карл Померанс "Проверка на простоту с гауссовыми периодами В архиве 2012-02-25 в Wayback Machine ", версия от 12 апреля 2011 г.
5. Дэниел Дж. Бернштейн "Доказательство первобытности после Агравал-Каял-Саксены ", версия от 25 января 2003 г.
6. Видеть AKS Talk страница для обсуждения того, почему отсутствует «Пример 2: n не является простым после шага 4».

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

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

внешняя ссылка

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