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

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

Свойства

Основным достижением авторов является то, что тест АКС является первым опубликованным алгоритмом проверки на простоту, который одновременно универсален, полиномиален, детерминирован и безусловен. Предыдущие алгоритмы обладали не более чем тремя из перечисленных свойств.

• Универсальность: Тест AKS может использоваться для проверки простоты любых чисел. Многие быстрые тесты предназначены для проверки чисел из ограниченного множества. Например, тест Люка — Лемера работает только для чисел Мерсенна, а тест Пепина применим лишь к числам Ферма.
• Полиномиальность: Наибольшее время работы алгоритма ограничено полиномом от количества цифр в проверяемом числе. Тесты ECPP (англ.) и APR (англ.) могут доказать или опровергнуть простоту числа, но для них не доказано, что время работы будет полиномиальным для любого входного числа.
• Детерминизм: Алгоритм гарантирует получение ответа. Вероятностные тесты, такие как тест Миллера — Рабина и тест BPSW (англ.), могут проверить простоту числа за полиномиальное время, но при этом дают лишь вероятностный ответ.
• Безусловность: Корректность теста AKS не зависит от каких-либо недоказанных гипотез. Напротив, тест Миллера детерминирован и работает за полиномиальное время для любого входного числа, но его корректность зависит от недоказанной обобщённой гипотезы Римана.

На практике тест не нашел широкого применения, так как его время работы оценивается как $\mathcal{O}$(log^7.5 n), где n — тестируемое число.

Теорема и алгоритм

Основная идея

Вместо кольца $\frac{Fp[x]}{x^r-1}$ рассматривают поле $F = \frac{Fp[x]}{h}$, где h = h(x) — неприводимый делитель ${x^r - 1}$ над полем Fp, отличный от $x-1$. Оценивают число многочленов этого поля, для которых выполняется соотношение вида $(x+a)^n=(x^n+a) \mod {(x^r-1,n)}$, и приходят к противоречию.

Алгоритм

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

1. Если n = a^b для целых чисел a > 0 и b > 1, вернуть составное.
2. Найдем наименьшее r такое что o_r(n) > log²(n).
3. Если 1 < НОД(a,n) < n для некоторого a ≤ r, вернуть составное.
4. Если n ≤ r, вернуть простое.
5. Для всех a от 1 до $\scriptstyle\lfloor \scriptstyle{\sqrt{\varphi(r)}\log(n)} \scriptstyle\rfloor$

   если (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), вернуть составное.

6. Вернуть простое.

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

Теорема

Алгоритм вернет простое тогда и только тогда когда n простое.

Улучшенный алгоритм

Ввод: n ∈ N, n > 1

1. Если n = a^b для a ∈ N и b > 1, вернуть составное.
2. Найдем наименьшее r такое что o_r(n) > log²(n)
3. Если НОД(a, n) ≠ 1 for all a ≤ r, вернуть составное.
4. Для всех a от 1 до $\mathcal b \sqrt{r}\log n \mathcal c$

   Если (X+a)ⁿ= Xⁿ+a (mod f(x),n), вернуть простое.

Используемые теоремы и леммы

Основным отправным пунктом является малая теорема Ферма и несколько лемм, доказанных в исходной статье. Приведем обозначения принятые в статье. Покажем условия лемм и несколько наиболее важных доказательств к ним.

Принятые обозначения

$G$ - группа всех чисел, которые являются вычетами для чисел из набора $I = \left \{ \left ( \frac{n}{p} \right )^i*p^j \mathcal j i,j \ge 0 \right \}$ по модулю r. Данная подгруппа уже содержит (n,r)=(p,r)=1. Так же $\mathcal j G \mathcal j = t$. Группа $G$ сгенерированна n, p по модулю r начиная с $o_r(n) > \log^2 n$, $t > log^2 n$.
Вторая группа - $\zeta$. Данная группа является набором всех вычетов полиномов в P (пространстве простых чисел) по модулю h(X) и p. Эта группа сгенерированна элементами X, X+1, X+2, ..., X+l в поле $F = \frac{F_p[X]}{h(X)}$ и является подгруппой мультипликативной группы F_p. Где F_p - конечное поле.

Леммы

1. Пусть а, n ∈ ℤ, n ≥ 2, и (a,n) = 1. Тогда n является простым тогда и только тогда, когда

   (X + a)ⁿ ≡ Xⁿ + a (mod n)

2. Пусть НОК(m), обозначает наименьшее общее кратное первых m чисел. Тогда для m ≥ 7 справедливо неравенство:

   НОК(m) ≥ 2^m

3. Если n простое, то алгоритм вернет prime.
4. Существует r такое, что $r \le \max \mathcal f 3,\mathcal d \log^5 n \mathcal e \mathcal g$, такое что $o_r(n) > \log^2n$.
5. Для полинома $f(X)$ и числа $m \in N$, говорится что m включено в $f(X)$, если $\mathcal d f(X) \mathcal e^m \equiv f(X^m) \pmod {X^r-1,\,p}$
6. Если числа m и m' включены в $f(X)$, то их произведение $m \cdot m'$ также включено
7. Если число m включено в $f(X)$ и $g(X)$, то m так же включено в $f(X) \cdot g(X)$
8. (Лемма Х. Ленстры (англ.)) $\mathcal j \zeta \mathcal j \ge \left ( ^{t+l} _{t-1} \right )$
9. Если n не является степенью p, то $\mathcal j \zeta \mathcal j \le n^\sqrt{t}$
10. Если алгоритм возвращает prime, то n простое

Доказательства

Лемма 1

$(X+a)^n=\sum^{n}_{i=0} {C^{i}_{n}X^{i}a^{n-i}}$, однако известно, для простого $n$ выполняется $C^{i}_{n}=0 (\bmod n)$ при $1 \le i \le {n-1}$. Кроме того, $a^n=a (\bmod n)$. Если же $n$ составное, a $q$ его простой делитель, то коэффициент при $X^q$ в левой части выражения не равен $0$.

Лемма 3

Если n простое, то на шагах 1 и 3 алгоритм никогда не выдаст COMPOSITE. По лемме 1 цикл алгоритма, так же не выдаст COMPOSITE. Следовательно, алгоритм определит, что n простое на шаге 4 или 6.

Лемма 4

Обозначим $K=log^2n$ и рассмотрим произведение $P=n*\prod^{K}_{j=1} {n^j-1}$. Число $P$ делится на некоторое $r$ тогда и только тогда, когда либо $n$ делится на $r$, либо при каком-то $j$ выполняется $n^j=1\bmod {r}$. Оценим величину ${P=n*\prod^{K}_{j=1} {n^j-1}} < {n*\prod^{K}_{j=1} {n^j}} = {\prod^{K+1}_{j=2} {n^j}} = {n^{\sum^{K+1}_{j=2} {j}}}$. Так как $\sum^{K+1}_{j=2} {j} = \frac{K*(K+3)}{2} < K^2$, то $P < n^{K^2} \le n^{\log^4 n} = 2^{\log^5 n}$. Возможны два случая: либо НОД( n, r)=1(НОД(n,r) обозначается как (n,r)) , и тогда $r$ — то самое, о существовании которого говорит лемма, либо ( n, r) > 1 . В последнем случае заметим, что $P$ делится на $n$ и не делится на $r$, значит, делится на ( n, r) и не делится на $s = \frac{r}{(n,r)}$. Число $s$ и будет требуемым, так как НОД( s,n)=1.

Лемма 10

Предположим, что алгоритм выдал PRIME. По лемме 8, для $t = \mathcal j G \mathcal j$ и $l = \mathcal b \sqrt{\varphi (r)} \log n \mathcal c$:
$\mathcal j \zeta \mathcal j \ge \left ( ^{t+l} _{t-1} \right ) \ge \left ( ^{l+1+\mathcal b \sqrt{t} \log n \mathcal c} _{\mathcal b \sqrt{t} \log n \mathcal c} \right ) (t > \sqrt{t} log n ) \ge \left ( ^{2 \mathcal b \sqrt{t} \log n \mathcal c +1} _{\mathcal b \sqrt{t} \log n \mathcal c} \right )( l = \mathcal b \sqrt{\varphi (r)} \log n \mathcal c \ge \mathcal b \sqrt{t} \log n \mathcal c ) >$ $> 2^{\mathcal b \sqrt{t} \log n \mathcal c +1}(\mathcal b \sqrt{t} \log n \mathcal c > \log^2 n \ge 1 ) \ge n^{\sqrt{t}}$
По лемме 9, $\mathcal j \zeta \mathcal j \le n^\sqrt{t}$ если n не степень числа p. По этой причине n=p^k для любых k>0. Если k>1, тогда алгоритм вернет COMPOSITE в шаге 1, следовательно n=p.

Время работы алгоритма

Время работы алгоритма в наихудшем случае оценивается как $\mathcal{O}$(log^10.5 n).^{[уточнить]}

В предположении верности гипотезы Артина, время выполнения улучшается до $\mathcal{O}$(log⁶ n).

В предположении верности гипотезы Софи Жермен, время также стремится к $\mathcal{O}$(log⁶ n).

Алгоритм требует $\mathcal{O}$(log^7.5 n).^{[уточнить]} Однако в 2005 году Померансом и Ленстрой (англ.) был предложен вариант алгоритма, который выполняется за $\mathcal{O}$(log⁶ n) и в 2011 году время работы алгоритма было улучшено до $\mathcal{O}$(log³ n) в статье "Primality Testing with Gaussian Periods".

Реализации

Реализация теста AKS в первоначальном и улучшенном варианте с использованием различных библиотек показаны в статье "An Implementation of the AKS Primality Test".
В данной статье сравнивались алгоритмы описанные в статьях «PRIMES is in P» и "Primality Testing with Gaussian Periods". В работе приведены реализации алгоритма на языке
С++. Так же сравнивались библиотеки NTL, LiDIA, GMU NTL, Apple/UMD. В статье приведены наглядные примеры в виде графиков и возможные улучшения в будущем.

Ссылки

• Л. Бараш Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. — 2005. — № 2. — С. 27-38.
• Weisstein, Eric W. AKS Primality Test (англ.) на сайте Wolfram MathWorld.
• R. Crandall, Apple ACG, J. Papadopoulos, On the implementation of AKS-class primality tests, 2003.
• JAVA implementation of the AKS Primality Test algorithm
• The AKS "PRIMES in P" Algorithm Resource
• Perl implementation of the AKS Primality Test
• Агафонова И. В. Проверка чисел на простоту: полиномиальный алгоритм // Семинар по дискретному гармоническому анализу и геометрическому моделированию.