Введение

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

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

• Полиномиальность означает, что сложность алгоритма ограничена полиномом от количества бит в числе. Примером теста, которые не удовлетворяет свойству полиномиальности, является тест Адлемана-Померанца-Румели.

• Универсальность подразумевает, что алгоритм применим к любым числам, а не только к числам специального вида. Примером неуниверсального алгоритма является тест Люка-Лемера, который применим только для чисел Мерсенна.

• Детерминированность означает, что алгоритм всегда выдаёт один и тот же ответ на одних и тех же входных данных. Примером недетерминированного (вероятностного) теста, может служить тест Миллера-Рабина.

• Безусловность — это независимость от недоказанных гипотез. Не удовлетворяет свойству безусловности, например, тест Миллера, который опирается на обобщённую гипотезу Римана.

Обозначения

- кольцо вычетов по модулю n.

Запись означает, что многочлены, коэффициенты которых рассматриваются как вычеты из , равны.

Запись означает, что многочлены с коэффициентами из равны по модулю многочлена .

— порядок числа n по модулю r. Минимальное число k, такое что .

— функция Эйлера. Количество натуральных чисел, меньших n и взаимно простых с ним.

— логарифм по основанию два числа n.

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

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

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

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

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

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

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

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

, при котором тождество

Выполнено для всех , то n — либо простое, либо степень простого.

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

Тест AKS

Алгоритм

Вход: натуральное число n > 1.
Выход: ПРОСТОЕ, если n — простое число. СОСТАВНОЕ в противном случае.

Алгоритм:

1. Если n — точная степень некоторого числа , вернуть СОСТАВНОЕ.

2. Найти наименьшее r, такое что .

3. Если 1 < НОД(a, n) < n для некоторого , вернуть СОСТАВНОЕ.

4. Если вернуть СОСТАВНОЕ.

5. Для каждого : Если вернуть СОСТАВНОЕ.

6. Вернуть ПРОСТОЕ.

Рассмотрим подробно реализацию каждого шага алгоритма и разберём выполнение на примере числа 47.

Шаг 1

На первом шаге нужно определить, является ли число n точной степенью другого числа, т. е. . Пожалуй, самый простой способ сделать это — проверить, что . При этом достаточно проверять только значения (так как если

, то )

function isPerfectPower(n)
{
    for (b = 2; b < ceil(log(n)); b++) {
        if (floor(n ** (1.0 / b)) ** b) == n:
            return true;
    }
    return false;
}

Пример:

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

Следовательно, 47 не является точной степенью другого числа.

Шаг 2

Подходящее r находится перебором. Для каждого r нужно:

1. Проверить, что для всех .

2. Если одно из значений равно единице — попробовать следующее r.

3. Если все не равны единице — r найдено.

Известно, что искомое r имеет порядок не более .

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++;
        }
    }
      
}

Пример:

Искомое r = 41:

Шаги 3-4

Элементарные, требуется только реализовать вычисление НОД двух чисел.

Шаг 5

Для достижения теоретической сложности достаточно использовать быстрые алгоритмы для арифметических операций с многочленами. Здесь рассмотрим одну эффективную на практике оптимизацию: нахождение остатка от деления без прямого деления многочленов, используя только сложения.

Если многочлен степени возводится в квадрат, то в результате получается многочлен степени :

Рассмотрим деление на :
, где

Раскрывая скобки, находим коэффициенты :

function mod (p) {
    for (i = p.degree(); i >= r; i--){
        p[i - r] = p[i - r] + p[i];
        p[i] = 0;
    }
}

Пример:

Оценка сложности

Введём обозначение: , где — некоторая функция от n.

При оценках будем опираться на то, что умножение и деление m-битных чисел имеют сложность . Соответственно, операции над полиномами степени d имеют сложность . НОД двух m-битных чисел можно найти за .

На первом шаге определение, является ли число точной степенью, имеет сложность .

На втором шаге нужно найти r. Это делается перебором возможных значений r и проверкой для всех . Для каждого r это требует умножений по модулю r, значит для каждого r сложность . Учитывая, что r имеет порядок , сложность всего шага равна .

Третий шаг требует вычисления НОД для r чисел. Общая сложность шага .

На пятом шаге нужно проверить равенств. Каждое равенство включает умножений полиномов степени r, у которых коэффициенты порядка . Каждое равенство может быть проверено за . Итого сложность шага .

Эту оценку из оригинальной статьи можно улучшить. Лучшая оценка на текущий момент .

Применение

Алгоритм AKS имеет важное теоретическое значение, однако не применяется на практике. Во-первых, оценка сложности содержит полином высокой степени. Во-вторых, алгоритм требователен по памяти. Даже при оценке параметра для проверки числа размером 1024 бит потребуется около 1 гигабайта памяти. Для практического применения лучше всего на данный момент использовать вероятностные алгоритмы.

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