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

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

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

Данный алгоритм имеет важное теоретическое значение, но на практике не применяется, так как его вычислительная сложность значительно выше, чем у лучших вероятностных алгоритмов[2].

Основные свойства[править | править вики-текст]

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

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

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

Детерминизм гарантирует получение ответа. Вероятностные тесты, такие как тест Миллера — Рабина и тест BPSW (англ.), могут проверить простоту числа за полиномиальное время, но при этом дают лишь вероятностный ответ.

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

Основная идея[править | править вики-текст]

Основной идеей алгоритма является обобщение малой теоремы Ферма на многочлены, утверждающее, что для a \in \Z_n^* (где кольцо \Z_n без обратных элементов по умножению — нулей) и n \in \N, n — простое тогда[1][3][4]:

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

Это выражение не может быть проверено за полиномиальное время. Кроме того, такой тест проходят некоторые классы псевдопростых чисел, включая числа Кармайкла[4]. Для сокращения сложности вычислений требуется выбрать такое r, чтобы использовать в качестве теста на простоту выражение:

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

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

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

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

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

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

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

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

Алгоритм[править | править вики-текст]

Ввод: целое число 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(\cdot) — функция Эйлера[6].

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

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

В 2011 году Ленстрой (англ.) опубликован улучшенный вариант алгоритма[7]:

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

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

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

Обоснование[править | править вики-текст]

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

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

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

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

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

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

  • Пусть а, n ∈ ℤ, n ⩾ 2, и (a,n) = 1. Тогда n является простым тогда и только тогда, когда
    (X + a)nXn + a (mod n).
  • Пусть НОК(m) обозначает наименьшее общее кратное первых m чисел. Тогда для m ⩾ 7 справедливо неравенство:
    НОК(m) ⩾ 2m.
  • Существует r такое, что  r \leqslant \max \big( 3, \lceil \log^5 n \rceil \big) , такое что  o_r(n) > \log^2n.
  • Определение. Для многочлена  f(X) и числа  m \in \N , говорится что m включено в  f(X) , если  \lceil f(X) \rceil ^m \equiv f(X^m) \pmod {X^r-1,\,p} .
  • Если числа m и m' включены в  f(X) , то их произведение m · m' также включено.
  • Если число m включено в  f(X) и  g(X) , то m так же включено в  f(X) \cdot g(X) .
  • (Лемма Ленстры) |\mathcal{G}| \geqslant \tbinom{t+l}{t-1}.
  • Если n не является степенью p, то |\mathcal G| \leqslant n^\sqrt{t} .

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

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

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

Критика[править | править вики-текст]

Алгоритм требует 1 000 000 000 Гб (гигабайт) памяти для чисел из 1024 бит, между тем алгоритмы, относящиеся к классу P, обычно считаются «лёгкими» для реализации. Проблема в том, что при отнесении алгоритма к полиномиальным учитывается только количество арифметических операций и не учитывается время ввода-вывода (в модели машины Тьюринга), что и делает некоторые полиномиальные алгоритмы совершенно непригодными для практической реализации[10]. Дональд Кнут, поместивший алгоритм в третий том Искусства программирования, в частной переписке отметил чисто теоретический характер алгоритма[10].

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 Agrawal, Kayal, Saxena, 2004
  2. 1 2 Бараш, 2005
  3. 1 2 Menon, 2013, pp. 10-11
  4. 1 2 3 4 Salembier, Southerington, 2005
  5. 1 2 Агафонова, 2009
  6. Menon, 2013, pp. 11-12
  7. 1 2 H. W. Lenstra jr. and Carl Pomerance, «Primality testing with Gaussian periods», version of April 12, 2011.
  8. 1 2 Agrawal, Kayal, Saxena, 2004, p. 5
  9. H. W. Lenstra, Jr. and Carl Pomerance, «Primality Testing with Gaussian Periods», preliminary version July 20, 2005.
  10. 1 2 Cao, Liu, 2014

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]