Processing math: 81%

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

Тест Агравала — Каяла — Саксены (тест 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), такое что 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\cdot 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 000000 000 Гб (гигабайт) памяти для чисел из 1024 бит. Для современныхоперационных систем это слишком большой объём информации. Впредположении верности гипотезы Артина и гипотезы Софи Жермен оплотности множества простых чисел для алгоритма будет достаточнозначения параметра r, оцениваемого в \mathcal{O}(\log^2 n). В этомслучае будет достаточно 1 Гб памяти. Но пока верность этих гипотез недоказана, алгоритм не применяется ввиду сложного исполнения. ДональдКнут, поместивший алгоритм во второй том Искусства программирования(издание 3), в частной переписке отметил его чисто теоретическийхарактер.