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

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

Формулировка


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

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

История


 Тест AKS был предложен индийским учёным и его двумя студентами и и впервые опубликован 6 августа 2002 года. До этой публикации принадлежность задачи распознавания простоты классу P являлась открытой проблемой.
 Вычислительная сложность изначального алгоритма оценивается как O(log21/2n). В предположении верности гипотезы Артина, время выполнения улучшается до O(log6n). В предположении верности гипотезы Софи Жермен время также стремится к O(log6n).
 В 2005 году и Померанс опубликовали улучшенный вариант алгоритма с вычислительной сложностью O(log6n), где n — проверяемое тестом число..
 Согласно существует вариант алгоритма с временем выполнения O(log3n), но Ленстра и Померанс привели эвристический аргумент, подтверждающий ложность этой гипотезы.
 Данный алгоритм имеет важное теоретическое значение, но на практике не применяется, так как его вычислительная сложность значительно выше, чем у лучших вероятностных алгоритмов. За своё открытие авторы получили премию Гёделя и премию Фалкерсона в 2006 году.

Основные свойства


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

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


 Основной идеей алгоритма является обобщение малой теоремы Ферма на многочлены, утверждающее, что для всех a\Zn (где кольцо \Zn взято без обратных элементов по умножению и нулевого элемента) и n\N, n — простое тогда и только тогда, когда :
 Иными словами, если a\Z, n\N, n2 и НОД(a,n)=1, то n простое тогда и только тогда, когда выполнено условие (1).
 На проверку этого выражения требуется время, оцениваемое в Ω(n), поскольку в худшем случае следует оценить n коэффициентов LHS. Для сокращения числа коэффициентов и сложности вычислений было выбрано такое r, чтобы использовать в качестве теста на простоту выражение:

(x+a)n(xn+a)(modxr1,n),
  которое получается делением обеих частей исходного выражения на xr1.
 Здесь количество подлежащих проверке значений a и значение r уже ограничены многочленом от logn.
 В этом случае вместо факторкольца Fp[x]/xr1 рассматривается поле F=Fp[x]/h, где h=h(x) — неприводимый делитель xr1 над конечным полем Fp, отличный от x1. Оценивается число многочленов этого поля, для которых выполняется сравнение:

(x+a)n(xn+a)(modxr1,n).

Алгоритм и его модификация



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

  1. Если n=ab для целых чисел a>0 и b>1, вернуть «составное».
  2. Найдем наименьшее r, такое что or(n)>log2(n).
  3. Если 1<НОД$(a,\;n)«составное».
  4. Если nr, вернуть «простое».
  5. Если для всех a от 1 до φ(r)log(n) верно, что (x+a)nxn+a(modxr1,n), вернуть «простое».
  6. Иначе вернуть «составное».

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

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

  1. Если n=ab для a\N и целого b>1, вернуть «составное».
  2. Найдем наименьшее r такое что or(n)>log2(n).
  3. Если НОД(a,n)1 для любого ar, вернуть «составное».
  4. Если для всех a от 1 до rlogn верно, что (x+a)nxn+a(modφ(x),n), вернуть «простое».
  5. Иначе вернуть «составное».

 Здесь функция φ(x) — та же, xr1 — многочлен степени, большей log2n, такой, что φ(xn)0(modφ(x)) при некоторых дополнительных условиях.
 Вычислительная сложность этого алгоритма — O(log6n).

Обоснование


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

I={(np)ipj:i,j0}.
  Данная подгруппа, назовём её группой G, уже содержит (n,r)=(p,r)=1. Группа G порождена n,p по модулю r, и так как or(n)>log2n, то |G|=t>log2n.
 Вторая группа, используемая в доказательстве, |G|, является множеством всех вычетов многочленов в P (пространстве простых чисел) по модулю h(x) и p. Эта группа порождена элементами x,x+1,x+2,,x+l в поле F=Fp[x]/h(x) и является подгруппой мультипликативной группы поля Fp.
 Основные промежуточные леммы и определения, используемые в обосновании алгоритма:

  • Пусть a,n\Z, n2, и НОД(a,n)=1. Тогда n является простым тогда и только тогда, когда
    (x+a)nxn+a(modn).
  • Пусть НОК(m) обозначает наименьшее общее кратное первых m чисел. Тогда для m7 справедливо неравенство:
      НОК(m)2m.
  • Существует r такое, что rmax(3,log5n), такое что or(n)>log2n.
  • Определение. Для многочлена f(x) и числа m\N, говорится что m включено в f(x), если f(x)mf(xm)(modxr1,p).
  • Если числа m и m включены в f(x), то их произведение mm также включено.
  • Если число m включено в f(x) и g(x), то m так же включено в f(x)g(x).
  • . |G|(t+lt1).
  • Если n не является степенью p, то |G|nt.

Практическое применение


 При оценке параметра r=O(log5n) алгоритм требует 1 000 000 000 Гб (гигабайт) памяти для чисел из 1024 бит. Для современных операционных систем это слишком большой объём информации. В предположении верности гипотезы Артина и гипотезы Софи Жермен о плотности множества простых чисел для алгоритма будет достаточно значения параметра r, оцениваемого в O(log2n). В этом случае будет достаточно 1 Гб памяти. Но пока верность этих гипотез не доказана, алгоритм не применяется ввиду сложного исполнения. Дональд Кнут, поместивший алгоритм во второй том Искусства программирования (издание 3), в частной переписке отметил его чисто теоретический характер.