Введение
Одной из важнейших задач в теории чисел является проверка числа на простоту. То есть по заданному числу эффективно определить является оно простым или составным. Алгоритмы, решающие эту задачу (их также называют тестами простоты), известны с древних времён, пример – решето Эратосфена. Но алгоритма, имеющего полиномиальную сложность, долгое время известно не было.
В 2002 году индийскими математиками Агравалом, Кайялом и Саксеной в работе “PRIMES is in P” был впервые предложен алгоритм проверки простоты чисел (известный как тест AKS), который одновременно является полиномиальным, универсальным, детерминированным и безусловным. До этого были известны алгоритмы, которые обладали максимум тремя из четырёх свойств.
Полиномиальность означает, что сложность алгоритма ограничена полиномом от количества бит в числе. Примером теста, которые не удовлетворяет свойству полиномиальности, является тест Адлемана-Померанца-Румели
Универсальность подразумевает, что алгоритм применим к любым числам, а не только к числам специального вида. Примером неуниверсального алгоритма является тест Люка-Лемера, который применим только для чисел Мерсенна
Детерминированность означает, что алгоритм всегда выдаёт один и тот же ответ на одних и тех же входных данных. Примером недетерминированного (вероятностного) теста, может служить тест Миллера-Рабина
Безусловность – это независимость от недоказанных гипотез. Не удовлетворяет свойству безусловности, например, тест Миллера, который опирается на обобщённую гипотезу Римана
Основная идея
Обозначения
$\mathbb {Z}_n$ - кольцо вычетов по модулю $n$
Запись $g(x) = h(x) \pmod{n}$ означает, что многочлены, коэффициенты которых рассматриваются как вычеты из $\mathbb {Z}_n$, равны
Запись $g(x) = h(x) \pmod{x^r - 1, n}$ означает, что многочлены с коэффициентами из $\mathbb {Z}_n$ равны по модулю многочлена $x^r - 1$
$ord_r(n)$ – порядок числа $n$ по модулю $r$. Минимальное число $k$, такое что $n^k = 1 \pmod{r}$
$\phi(n)$ – функция Эйлера. Количество натуральных чисел, меньших $n$ и взаимно простых с ним
$\log(n)$ – логарифм по основанию два числа $n$
Основная идея алгоритма опирается на следующую теорему:
Теорема:
$$(x + a)^n = x^n + a \pmod{n}$$ выполняется тогда и только тогда, когда $n$ – простое.
∎
Это тождество уже можно использовать для проверки простоты. Но алгоритм не будет полиномиальным, так как потребуется сделать $O(n)$ проверок – по числу коэффициентов в полиномах. Идея состоит в том, чтобы рассматривать равенство полиномов по модулю другого полинома, степени меньшей, чем $n$. Из теоремы вытекает следствие:
Следствие:
∎
Обратное утверждение в общем случае неверно. В статье индийских математиков доказано, что для некоторого $r$ и некоторого множества значений $a$ обратное утверждение будет верно:
Теорема:
∎
Это позволяет построить полиномиальный алгоритм проверки чисел на простоту, что является основным результатом работы.
Тест AKS
Алгоритм
Вход: натуральное число $n > 1$
Выход: ПРОСТОЕ, если $n$ – простое число. СОСТАВНОЕ в противном случае
Алгоритм:
- Если $n$ – точная степень некоторого числа ($n = a^b, a, b \in \mathbb {N}, b > 1)$, вернуть СОСТАВНОЕ
- Найти наименьшее $r$, такое что $ord_{r}(n) > \log^2 n$
- Если $1 < (a, n) < n$ для некоторого $a \le r$, вернуть СОСТАВНОЕ
- Если $n \le r$ вернуть СОСТАВНОЕ
- Для каждого $1 \le a \le \left \lfloor {\sqrt{\phi(r)}\log n} \right \rfloor $:
Если $(x + a)^n \ne x^n + a \pmod{x^r - 1, n} $ вернуть СОСТАВНОЕ - Вернуть ПРОСТОЕ
Рассмотрим подробно реализацию каждого шага алгоритма и разберём выполнение на примере числа 47.
Шаг 1
На первом шаге нужно определить, является ли число $n$ точной степенью другого числа, т. е. $n = a^b$. Пожалуй, самый простой способ сделать это – проверить, что $\left \lfloor n^{1/b} \right \rfloor^b \ne n$. При этом достаточно проверять только значения $2 \le b < \log n$ (так как если $b >\log n$, то $2^b > n$)
function isPerfectPower(n)
{
for (b = 2; b < ceil(log(n)); b++) {
if (floor(n ** (1.0 / b)) ** b) == n:
return true;
}
return false;
}
Пример:
$\left \lfloor \log 47 \right \rfloor = 5$
$\left \lfloor 47^{1/2} \right \rfloor^2 = 36$
$\left \lfloor 47^{1/3} \right \rfloor^3 = 27$
$\left \lfloor 47^{1/4} \right \rfloor^4 = 16$
Следовательно, 47 не является точной степенью другого числа.
∎
Шаг 2
Подходящее $r$ находится перебором. Для каждого $r$ нужно:
- Проверить, что $n^k \ne 1 \pmod{r}$ для всех $k \le \lfloor \log^2n \rfloor$
- Если одно из значений равно единице – попробовать следующее $r$
- Если все не равны единице – $r$ найдено
Известно, что искомое $r$ имеет порядок не более $O(\log^5 n)$.
function findR(n) {
r = 2;
while (true) {
find = true;
for (k = 1; k < ceil(log(n) ** 2); k++) {
if (n ** k % r == 1) {
find = false;
break
}
}
if (find) {
return r;
} else {
r++;
}
}
}
Пример:
$\lfloor \log^2 47 \rfloor = 32$
Искомое $r = 41$:
$47^{1} \pmod{41} = 6$
$47^{2} \pmod{41} = 36$
$ \ldots $
$47^{32} \pmod{41} = 37$
∎
Шаги 3-4
Элементарные, требуется только реализовать вычисление НОД двух чисел.
Шаг 5
Для достижения теоретической сложности достаточно использовать быстрые алгоритмы для арифметических операций с многочленами. Здесь рассмотрим одну эффективную на практике оптимизацию: нахождение остатка от деления без прямого деления многочленов, используя только сложения.
Если многочлен степени $r - 1$ возводится в квадрат, то в результате получается многочлен степени $2r-2$:
$f(x) = c_{2r-2}x^{2r-2} + \ldots + c_rx^r +c_{r - 1}x^{r-1} + c_{r-1}x^{r-1} + \ldots + c_1x + c_0$
Рассмотрим деление на $x^r - 1$:
$f(x) = a(x)(x^r - 1) + b(x)$, где
$a(x) = a_{r-2}x^{r-2} + \ldots + a_0$
$b(x) = b_{r-2}x^{r-2} + \ldots + b_0$
Раскрывая скобки, находим коэффициенты $b$:
$b_0 = c_0 + a_0 = c_0 + c_r$
$b_1 = c_1 + a_1 = c_1 + c_{1 + r}$
$\ldots$
$b_{r - 2} = c_{r - 2} + a_{r - 2} = c_{r - 2} + c_{2r - 2}$
function mod (p) {
for (i = p.degree(); i >= r; i--){
p[i - r] = p[i - r] + p[i];
p[i] = 0;
}
}
Пример:
$ \left \lfloor {\sqrt{\phi(41)}\log 41} \right \rfloor = 36$
$a = 1: (x + 1)^{47} = x^{47} + 1 \pmod{x^{41} - 1, 47} = x^6+1 $
$a = 2: (x + 2)^{47} = x^{47} + 2 \pmod{x^41 - 1, 47} = x^6+2 $
$ \ldots $
$a = 36: (x + 36)^{47} = x^{47} + 36 \pmod{x^{41} - 1, 47} = x^6+36 $
∎
Оценка сложности
Введём обозначение: $\widetilde{O}(t(n)) = O(t(n) \cdot poly(\log(t(n))))$, где $t(n)$ – некоторая функция от $n$.
При оценках будем опираться на то, что умножение и деление m-битных чисел имеют сложность $\widetilde{O}(m)$. Соответственно, операции над полиномами степени $d$ имеют сложность $\widetilde{O}(dm)$. НОД двух m-битных чисел можно найти за $O(\log n)$.
На первом шаге определение, является ли число точной степенью, имеет сложность $\widetilde{O}(\log^3n)$.
На втором шаге нужно найти $r$. Это делается перебором возможных значений $r$ и проверкой $n^k \ne 1 \pmod{r}$ для всех $k \le \log^2n$. Для каждого $r$ это требует $O(\log^2n)$ умножений по модулю $r$, значит для каждого $r$ сложность $\widetilde{O}(\log^2n \log r)$. Учитывая, что $r$ имеет порядок $O(\log^5n)$, сложность всего шага равна $\widetilde{O}(\log^7n)$.
Третий шаг требует вычисления НОД для $r$ чисел. Общая сложность шага $O(r \log n) = O(\log^6 n)$.
На пятом шаге нужно проверить $\left \lfloor {\sqrt{\phi(n)}\log n} \right \rfloor $ равенств. Каждое равенство включает $O(\log n)$ умножений полиномов степени $r$, у которых коэффициенты порядка $O(\log n)$. Каждое равенство может быть проверено за $\widetilde{O}(r \log^2 n)$. Итого сложность шага $\widetilde{O}(r \sqrt{\phi (r)} \log^3 n) = \widetilde{O}(r^{3/2} \log^3 n) = \widetilde{O}(\log^{21/2}n)$.
Эту оценку из оригинальной статьи можно улучшить. Лучшая оценка на текущий момент $\widetilde{O}(\log^6n)$.
Применение
Алгоритм AKS имеет важное теоретическое значение, однако не применяется на практике. Во-первых, оценка сложности содержит полином высокой степени. Во-вторых, алгоритм требователен по памяти. Даже при оценке параметра $r = O(\log^2{n})$ для проверки числа размером 1024 бит потребуется около 1 гигабайта памяти. Для практического применения лучше всего на данный момент использовать вероятностные алгоритмы.