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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Тест AKS»)
Перейти к: навигация, поиск

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

Свойства[править | править исходный текст]

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

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

На практике тест не нашел широкого применения, так как его время работы оценивается как \mathcal{O}(log7.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 = ab для целых чисел a > 0 и b > 1, вернуть составное.
  2. Найдем наименьшее r такое что or(n) > log2(n).
  3. Если 1 < НОД(a,n) < n для некоторого ar, вернуть составное.
  4. Если nr, вернуть простое.
  5. Для всех a от 1 до \scriptstyle\lfloor \scriptstyle{\sqrt{\varphi(r)}\log(n)} \scriptstyle\rfloor
    если (X+a)nXn+a (mod Xr − 1,n), вернуть составное.
  6. Вернуть простое.

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

Теорема[править | править исходный текст]

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

Улучшенный алгоритм[2][править | править исходный текст]

Ввод: n ∈ N, n > 1
  1. Если n = ab для a ∈ N и b > 1, вернуть составное.
  2. Найдем наименьшее r такое что or(n) > log2(n)
  3. Если НОД(a, n) ≠ 1 for any a ≤ r, вернуть составное.
  4. Для всех a от 1 до \mathcal b \sqrt{r}\log n \mathcal c
    Если (X+a)n= Xn+a (mod f(x),n), вернуть простое.

Используемые теоремы и леммы[править | править исходный текст]

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

Принятые обозначения[править | править исходный текст]

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)} и является подгруппой мультипликативной группы Fp. Где Fp - конечное поле.

Леммы[править | править исходный текст]

  1. Пусть а, n ∈ ℤ, n ≥ 2, и (a,n) = 1. Тогда n является простым тогда и только тогда, когда
    (X + a)nXn + a (mod n)
  2. Пусть НОК(m), обозначает наименьшее общее кратное первых m чисел. Тогда для m ≥ 7 справедливо неравенство:
    НОК(m) ≥ 2m
  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=pk для любых k>0. Если k>1, тогда алгоритм вернет COMPOSITE в шаге 1, следовательно n=p.

Время работы алгоритма[править | править исходный текст]

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

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

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

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

Реализации[править | править исходный текст]

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

Примечания[править | править исходный текст]

  1. 1 2 3 4 Manindra Agrawal, Neeraj Kayal, Nitin Saxena PRIMES is in P // Annals of Mathematics. — 2004. — Т. 160. — № 2. — С. 781–793.
  2. 1 2 3 H. W. Lenstra jr. and Carl Pomerance, "Primality testing with Gaussian periods", version of April 12, 2011.
  3. H. W. Lenstra, Jr. and Carl Pomerance, «Primality Testing with Gaussian Periods», preliminary version July 20, 2005.
  4. Robert G. Salembier and Paul Southerington, "An Implementation of the AKS Primality Test"

Ссылки[править | править исходный текст]