Эта статья входит в число добротных статей

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

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

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

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

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

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

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

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 над целыми числами[1].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

(1)

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

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

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

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

Здесь количество подлежащих проверке значений a и значение r уже ограничены многочленом от \log n[8]. В этом случае вместо факторкольца \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}.

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

Ввод: целое число 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. Иначе вернуть «составное».

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

Ленстра (нидерл. Hendrik Lenstra) и Померанс опубликовали улучшенный вариант алгоритма[8][4]:

Ввод: 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), вернуть «простое».
  5. Иначе вернуть «составное».

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

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

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

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

 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[9].

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

  • Пусть а, 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} .

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

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

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

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

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

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

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