Полиномиальный алгоритм проверки чисел на простоту: тест Агравала-Каяла-Саксены

Введение

Одной из важнейших задач в теории чисел является проверка числа на простоту. То есть по заданному числу эффективно определить, является оно простым или составным. Алгоритмы, решающие эту задачу (их также называют тестами простоты), известны с древних времён, например решето Эратосфена. Но алгоритма, имеющего полиномиальную сложность, долгое время известно не было.

В 2002 году индийскими математиками Агравалом, Кайялом и Саксеной в работе «PRIMES is in P» был впервые предложен алгоритм проверки простоты чисел, который одновременно является полиномиальным, универсальным, детерминированным и безусловным. До этого были известны алгоритмы, которые обладали максимум тремя из четырёх свойств.

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

Обозначения

$\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.

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

Основная идея алгоритма опирается на следующую теорему:

Теорема:
Если числа a и n взаимно просты, то тождество

$(x + a)^n = x^n + a \pmod{n}$

выполняется тогда и только тогда, когда n — простое.

Это тождество уже можно использовать для проверки простоты. Но алгоритм не будет полиномиальным, так как потребуется сделать O(n) проверок — по числу коэффициентов в полиномах. Идея состоит в том, чтобы рассматривать равенство полиномов по модулю другого полинома, степени меньшей, чем n. Из теоремы вытекает следствие:

Следствие:
Если n простое, то для любого натурального r и любого натурального 0 < a < n выполняется

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

Обратное утверждение в общем случае неверно. В статье индийских математиков доказано, что для некоторого r и некоторого множества значений a обратное утверждение будет верно:

Теорема:
Если существует r, такое что

$ord_{r}(n) > \log^2 n$ , при котором тождество

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

Выполнено для всех $1 \le a \le \left \lfloor {\sqrt{\phi(n)}\log n} \right \rfloor$ , то n — либо простое, либо степень простого.

Это позволяет построить полиномиальный алгоритм проверки чисел на простоту, что является основным результатом работы.

Тест 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$

Проверяем от 2 до 4:

$\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_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 гигабайта памяти. Для практического применения лучше всего на данный момент использовать вероятностные алгоритмы.

Канал с дополнительными материалами.

ссылка на оригинал статьи https://habr.com/ru/articles/855792/