Тест Агравала — Каяла — Саксены

Тест Аграва́ла — Кая́ла — Саксе́ны (тест AKS) — единственный известный на данный момент универсальный (то есть применимый ко всем числам) полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

Если существует ${\displaystyle r\in \mathbb {Z} }$ такое, что ${\displaystyle o_{r}(n)>\log ^{2}n}$ и для любого ${\displaystyle a}$ от 1 до ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log(n)\right\rfloor }$ выполняется сравнение ${\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n}}}$,
то ${\displaystyle n}$ — либо простое число, либо степень простого числа.

Здесь и далее ${\displaystyle o_{r}(n)}$ обозначает показатель числа ${\displaystyle n}$ по модулю ${\displaystyle r}$, ${\displaystyle \log }$ — двоичный логарифм и ${\displaystyle \varphi (\cdot )}$ — функция Эйлера^[1].

Сравнение по двум модулям вида

${\displaystyle a(x)\equiv b(x){\pmod {h(x),\;n}}}$

для многочленов ${\displaystyle a(x),\;b(x)\in \mathbb {Z} [x]}$ означает, что существует ${\displaystyle g(x)\in \mathbb {Z} [x]}$ такой, что все коэффициенты многочлена ${\displaystyle a(x)-b(x)-g(x)h(x)}$ кратны ${\displaystyle n}$, где ${\displaystyle \mathbb {Z} [x]}$ — кольцо многочленов от ${\displaystyle x}$ над целыми числами^[1].

Тест AKS был предложен индийским учёным Мани́ндрой Аграва́лом^[англ.] и его двумя студентами Ни́раджем Кая́лом^[англ.] и Нити́ном Саксе́ной^[англ.] Индийского технического института Канпура^[англ.] и впервые опубликован 6 августа 2002 года^[2]. До этой публикации принадлежность задачи распознавания простоты классу P являлась открытой проблемой.

Вычислительная сложность изначального алгоритма оценивается как ${\displaystyle {\mathcal {O}}(\log ^{21/2}n)}$. В предположении верности гипотезы Артина, время выполнения улучшается до ${\displaystyle {\mathcal {O}}(\log ^{6}n)}$. В предположении верности гипотезы Софи Жермен время также стремится к ${\displaystyle {\mathcal {O}}(\log ^{6}n)}$^[2].

В 2005 году Ленстра и Померанс опубликовали улучшенный вариант алгоритма с вычислительной сложностью ${\displaystyle {\mathcal {O}}(\log ^{6}n)}$, где ${\displaystyle n}$ — проверяемое тестом число^[3][4].

Согласно гипотезе Агравала существует вариант алгоритма с временем выполнения ${\displaystyle {\mathcal {O}}(\log ^{3}n)}$, но Ленстра и Померанс привели эвристический аргумент, подтверждающий ложность этой гипотезы^[2].

Данный алгоритм имеет важное теоретическое значение, но на практике не применяется, так как его вычислительная сложность значительно выше, чем у лучших вероятностных алгоритмов^[5]. За своё открытие авторы получили премию Гёделя и премию Фалкерсона в 2006 году^[6].

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

Универсальность теста означает, что он может использоваться для проверки простоты любых чисел. Многие быстрые тесты предназначены для проверки чисел из ограниченного множества. Например, тест Люка — Лемера работает только для чисел Мерсенна, а тест Пепина применим лишь к числам Ферма^[6].

Полиномиальность означает, что наибольшее время работы алгоритма ограничено многочленом от количества цифр в проверяемом числе. При этом такие тесты, как тест эллиптических кривых (ECPP) и тест Адлемана — Померанса — Румели (APR), могут доказать или опровергнуть простоту числа, но для них не доказано, что время работы будет полиномиальным для любого входного числа^[6].

Детерминизм гарантирует получение уникального предопределённого результата. Вероятностные тесты, такие, как тест Миллера — Рабина и тест Бейли — Померанца — Селфриджа — Уогстаффа, могут проверить простоту числа за полиномиальное время, но при этом дают лишь вероятностный ответ^[6].

Безусловность — свойство, заключающееся в том, что корректность алгоритма не зависит от каких-либо недоказанных гипотез. Этим свойством не обладает, например, Тест Миллера, который хоть и детерминирован и работает за полиномиальное время для любого входного числа, но его корректность зависит от недоказанной обобщённой гипотезы Римана^[6].

Основной идеей алгоритма является обобщение малой теоремы Ферма на многочлены, утверждающее, что для всех ${\displaystyle a\in \mathbb {Z} _{n}^{*}}$ (где кольцо ${\displaystyle \mathbb {Z} _{n}}$ взято без обратных элементов по умножению и нулевого элемента) и ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle n}$ — простое тогда и только тогда, когда^[2][7][8]:

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

1

Иными словами, если ${\displaystyle a\in \mathbb {Z} }$, ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle n\geqslant 2}$ и НОД${\displaystyle (a,\;n)=1}$, то ${\displaystyle n}$ простое тогда и только тогда, когда выполнено условие (1).

На проверку этого выражения требуется время, оцениваемое в ${\displaystyle \Omega (n)}$, поскольку в худшем случае следует оценить ${\displaystyle n}$ коэффициентов в левой части. Для сокращения числа коэффициентов и сложности вычислений было выбрано такое ${\displaystyle r}$, чтобы использовать в качестве теста на простоту выражение^[2]:

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

которое получается делением обеих частей исходного выражения на ${\displaystyle x^{r}-1}$^[7].

Здесь количество подлежащих проверке значений ${\displaystyle a}$ и значение ${\displaystyle r}$ уже ограничены многочленом от ${\displaystyle \log n}$^[8].

В этом случае вместо факторкольца ${\displaystyle \mathbb {F} _{p}[x]/\langle x^{r}-1\rangle }$ рассматривается поле ${\displaystyle F=\mathbb {F} _{p}[x]/\langle h\rangle }$, где ${\displaystyle h=h(x)}$ — неприводимый делитель ${\displaystyle {x^{r}-1}}$ над конечным полем ${\displaystyle \mathbb {F} _{p}}$, отличный от ${\displaystyle x-1}$. Оценивается число многочленов этого поля, для которых выполняется сравнение:

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

Ввод: целое число ${\displaystyle n>1}$.

1. Если ${\displaystyle n=a^{b}}$ для целых чисел ${\displaystyle a>1}$ и ${\displaystyle b>1}$, вернуть «составное».
2. Найдем наименьшее ${\displaystyle r}$, такое что ${\displaystyle o_{r}(n)>(\log _{2}(n))^{2}}$.
3. Если ${\displaystyle 1<}$НОД${\displaystyle (a,\;n)<n}$ для некоторого ${\displaystyle a\leqslant r}$, вернуть «составное».
4. Если ${\displaystyle n\leqslant r}$, вернуть «простое».
5. Если для всех ${\displaystyle a}$ от 1 до ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log(n)\right\rfloor }$ верно, что ${\displaystyle (x+a)^{n}\equiv x^{n}+a{\pmod {x^{r}-1,\;n}}}$, вернуть «простое».
6. Иначе вернуть «составное».

Агравалом, Каялом и Саксеной доказано, что алгоритм вернёт «простое» тогда и только тогда, когда ${\displaystyle n}$ — простое число.

Ленстра и Померанс опубликовали улучшенный вариант алгоритма^[8][4]:

Ввод: ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle n>1}$

1. Если ${\displaystyle n=a^{b}}$ для ${\displaystyle a\in \mathbb {N} }$ и целого ${\displaystyle b>1}$, вернуть «составное».
2. Найдем наименьшее ${\displaystyle r}$ такое что ${\displaystyle o_{r}(n)>(log_{2}(n))^{2}}$.
3. Если НОД${\displaystyle (a,\;n)\neq 1}$ для любого ${\displaystyle a\leqslant r}$, вернуть «составное».
4. Если для всех ${\displaystyle a}$ от 1 до ${\displaystyle \left\lfloor {\sqrt {r}}\log n\right\rfloor }$ верно, что ${\displaystyle (x+a)^{n}\equiv x^{n}+a{\pmod {\varphi (x),\;n}}}$, вернуть «простое».
5. Иначе вернуть «составное».

Здесь функция ${\displaystyle \varphi (x)}$ — та же, ${\displaystyle x^{r}-1}$ — многочлен степени, большей ${\displaystyle \log ^{2}n}$, такой, что ${\displaystyle \varphi (x^{n})\equiv 0{\pmod {\varphi (x)}}}$ при некоторых дополнительных условиях^[1][8].

Вычислительная сложность этого алгоритма — ${\displaystyle {\mathcal {O}}(\log ^{6}n)}$.

В обосновании используется группа ${\displaystyle G}$ — группа всех чисел, которые являются вычетами по модулю ${\displaystyle r}$ для чисел из набора^[9]:

${\displaystyle I=\left\{\left({\frac {n}{p}}\right)^{i}\cdot p^{j}\colon i,\;j\geqslant 0\right\}.}$

Данная подгруппа, назовём её группой ${\displaystyle G}$, уже содержит ${\displaystyle (n,\;r)=(p,\;r)=1}$. Группа ${\displaystyle G}$ порождена ${\displaystyle n,p}$ по модулю ${\displaystyle r}$, и так как ${\displaystyle o_{r}(n)>\log ^{2}n}$, то ${\displaystyle |G|=t>\log ^{2}n}$.

Вторая группа, используемая в доказательстве, ${\displaystyle |{\mathcal {G}}|}$, является множеством всех вычетов многочленов в ${\displaystyle P}$ (пространстве простых чисел) по модулю ${\displaystyle h(x)}$ и ${\displaystyle p}$. Эта группа порождена элементами ${\displaystyle x,\;x+1,\;x+2,\;\ldots ,\;x+l}$ в поле ${\displaystyle F=\mathbb {F} _{p}[x]/\langle h(x)\rangle }$ и является подгруппой мультипликативной группы поля ${\displaystyle \mathbb {F} _{p}}$^[9].

Основные промежуточные леммы и определения, используемые в обосновании алгоритма^[2]:

• Пусть ${\displaystyle a,\;n\in \mathbb {Z} }$, ${\displaystyle n\geqslant 2}$, и НОД${\displaystyle (a,\;n)=1}$. Тогда ${\displaystyle n}$ является простым тогда и только тогда, когда

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

• Пусть НОК${\displaystyle (m)}$ обозначает наименьшее общее кратное первых ${\displaystyle m}$ чисел. Тогда для ${\displaystyle m\geqslant 7}$ справедливо неравенство:

  НОК${\displaystyle (m)\geqslant 2^{m}.}$

• Существует ${\displaystyle r}$ такое, что ${\displaystyle r\leqslant \max {\big (}3,\;\lceil \log ^{5}n\rceil {\big )}}$, такое что ${\displaystyle o_{r}(n)>\log ^{2}n}$.
• Определение. Для многочлена ${\displaystyle f(x)}$ и числа ${\displaystyle m\in \mathbb {N} }$, говорится что ${\displaystyle m}$ включено в ${\displaystyle f(x)}$, если ${\displaystyle \lceil f(x)\rceil ^{m}\equiv f(x^{m}){\pmod {x^{r}-1,\;p}}}$.
• Если числа ${\displaystyle m}$ и ${\displaystyle m'}$ включены в ${\displaystyle f(x)}$, то их произведение ${\displaystyle m\cdot m'}$ также включено.
• Если число ${\displaystyle m}$ включено в ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$, то ${\displaystyle m}$ так же включено в ${\displaystyle f(x)\cdot g(x)}$.
• Лемма Ленстры. ${\displaystyle |{\mathcal {G}}|\geqslant {\tbinom {t+l}{t-1}}}$.
• Если ${\displaystyle n}$ не является степенью ${\displaystyle p}$, то ${\displaystyle |{\mathcal {G}}|\leqslant n^{\sqrt {t}}}$.

При оценке параметра ${\displaystyle r={\mathcal {O}}(\log ^{5}n)}$ алгоритм требует 1 000 000 000 Гб (гигабайт) памяти для чисел из 1024 бит. Для современных операционных систем это слишком большой объём информации. В предположении верности гипотезы Артина и гипотезы Софи Жермен о плотности множества простых чисел для алгоритма будет достаточно значения параметра ${\displaystyle r}$, оцениваемого в ${\displaystyle {\mathcal {O}}(\log ^{2}n)}$. В этом случае будет достаточно 1 Гб памяти. Но пока верность этих гипотез не доказана, алгоритм не применяется ввиду сложного исполнения. Дональд Кнут, поместивший алгоритм во второй том Искусства программирования (издание 3), в частной переписке отметил его чисто теоретический характер^[6].

• Бараш Л. Ю. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. — 2005. — № 2. — С. 27—38. Архивировано 18 октября 2014 года.
• Агафонова И. В. Проверка чисел на простоту: полиномиальный алгоритм // Семинар по дискретному гармоническому анализу и геометрическому моделированию. — 2009.

на английском языке

• Agrawal M., Kayal N., Saxena N. PRIMES is in P (англ.) // Annals of Mathematics / J. Bourgain — Princeton University, 2004. — Vol. 160, Iss. 2. — P. 781–793. — ISSN 0003-486X; 1939-8980 — doi:10.4007/ANNALS.2004.160.781
• R. Crandall, Apple ACG, J. Papadopoulos, On the implementation of AKS-class primality tests, 2003.
• Salembier R. G., Southerington P. An Implementation of the AKS Primality Test — 2005.  — сравнение реализаций изначального алгоритма и алгоритма Ленстры с использованием различных библиотек.
• Zhengjun Cao, Lihua Liu. Remarks on AKS Primality Testing Algorithm and A Flaw in the Definition of P. — 2014. — arXiv:1402.0146v1.
• Granville A. It is easy to determine whether a given integer is prime (англ.) // Bulletin (new series) of the American Mathematical Society. / S. Friedlander — Providence: American Mathematical Society, 2005. — Vol. 42, Iss. 1. — P. 3—38. — ISSN 0273-0979; 1088-9485 — doi:10.1090/S0273-0979-04-01037-7
• Agrawal, M. and Kayal, N. and Saxena, N. Polynomial time deterministic method for testing primality of numbers (англ.). Patent US 20050027764 A1. Дата обращения: 15 декабря 2013.
• Rotella C. An efficient implementation of the aks polynomial-time primality proving algorithm (англ.). — Pittsburgh, Pennsylvania, USA: School of Computer Science-Carnegie Mellon University, 2005.
• Vijay Menon. Deterministic Primality Testing — understanding the AKS algorithm (англ.) // CoRR. — 2007. — Vol. abs/1311.3785.

• Weisstein, Eric W. AKS Primality Test (англ.) на сайте Wolfram MathWorld. — краткая информация о тесте AKS
• Phil Carmody. The AKS «PRIMES in P» Algorithm Resource (англ.). Дата обращения: 19 октября 2014. — обзор материалов, посвящённых алгоритму
• Li, H. The Analysis and Implementation of the AKS Algorithm and Its Improvement Algorithms (англ.). — 2013.
• Pedro Berrizbetia. Sharpening «Primes is in P» for a large family of numbers. (англ.). — 2011.