AKS primality test

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

Важность

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

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

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

Концепции

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

(X+a)^{n}\equiv X^{n}+a{\pmod {n}}

( 1 )

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

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

{n \choose k}\equiv 0{\pmod {n}}

для всех

0<k<n

если

n

является простым.

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

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

(X+a)^{n}\equiv (X^{n}+a){\pmod {X^{r}-1,n}}

( 2 )

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

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

( 3 )

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

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

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

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

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

В ответ на некоторые из этих вариантов, а также на другие отзывы, статья «ПРАЙМЫ в P» была дополнена новой формулировкой алгоритма AKS и доказательством его корректности. (Эта версия в конечном итоге была опубликована в «Анналах математики» .) Хотя основная идея осталась прежней, r было выбрано по-новому, а доказательство правильности было организовано более последовательно. Новое доказательство опиралось почти исключительно на поведение круговых многочленов над конечными полями . Новая верхняя граница временной сложности составила ${\tilde {O}}(\log(n)^{10.5})$ , позже приведенный с использованием дополнительных результатов теории решета к ${\tilde {O}}(\log(n)^{7.5})$ .

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

Алгоритм

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

Входные данные: целое число

n > 1

.

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

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

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

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

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

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

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

Схема подтверждения действительности

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

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

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

   Input: integer n = 31 > 1.

   (* Step 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}

   (* Step 2 *)
   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

   (* Step 3 *)
   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

   (* Step 4 *)
   If (n ≤ r), 
     output prime.
     If (n ≤ r), 
       Return[Prime] (* this step may be omitted if n > 5690034 *)
      
     31 > 29
   
   (* Step 5 *)
   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)}
   
   (* Step 6 *)
   Output prime.
     31 Must be Prime

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

^[6]

Ссылки

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

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

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

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

[AKS-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF ) Анналы математики 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR 3597229 .

[2] Гранвилл, Эндрю (2005). «Легко определить, является ли данное целое число простым» . Бык. амер. Математика. Соц . 42 : 3–38. дои : 10.1090/S0273-0979-04-01037-7 .

[lenstra_pomerance_2005-3] HW Ленстра-младший и Карл Померанс, « Тестирование простоты с гауссовыми периодами », предварительная версия, 20 июля 2005 г.

[lenstra_pomerance_2011-4] HW Ленстра-младший и Карл Померанс, « Тестирование простоты с гауссовскими периодами. Архивировано 25 февраля 2012 г. в Wayback Machine », версия от 12 апреля 2011 г.

[bernstein03-5] Дэниел Дж. Бернштейн, « Доказательство первичности после Агравала-Каяла-Саксены », версия от 25 января 2003 г.

[6] См . страницу обсуждения AKS , где обсуждается, почему отсутствует «Пример 2: n не является простым после шага 4».

[1]

[2]

[3]

[4]

[5]

[6]

v т и Теоретико-числовые алгоритмы
Тесты на примитивность	АКС АПРЕЛЬ Бэйли – PSW Эллиптическая кривая Поклингтон Ферма Лукас Лукас-Лемер Лукас-Лемер-Ризель Теорема Прота Пепина Квадратичный Фробениус Solovay–Strassen Миллер-Рабин
Прайм-генерирующий	Сито Аткина Решето Эратосфена Сито Причарда Решето Сундарама Факторизация колес
Целочисленная факторизация	Непрерывная дробь (CFRAC) Диксона Эллиптическая кривая Ленстры (ECM) Эйлера Ро Полларда п - 1 р + 1 Квадратное сито (QS) Сито общего числового поля (GNFS) Сито специального числового поля (SNFS) Рациональное сито Ферма Квадратные формы Шанкса Пробное подразделение Шора
Умножение	Древний Египет Длинный Карацуба Тум-Кук Улицы Шенхаге Фюрера
Евклидово деление	Двоичный Разбивка на части Фурье Гольдшмидт Ньютон-Рафсон Длинный Короткий СТО
Дискретный логарифм	Бэби-шаг, гигантский шаг Поллард Ро Поллард кенгуру Полиг-Хеллман Индексное исчисление Функциональное поле сита
Наибольший общий делитель	Двоичный евклидов Расширенный евклидов Лемерс
Модульный квадратный корень	Лук Поклингтон Тонелли – Шанкс Берлекамп Кунерт
Другие алгоритмы	Чакравала Ворона Возведение в степень возведением в степень Целочисленный квадратный корень Целочисленное отношение ( LLL ; KZ ) Модульное возведение в степень Сокращение Монтгомери Пучок Система Трахтенберга
Курсивом обозначено, что алгоритм предназначен для чисел специальных форм.