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

2024-11-08 12:50

Теория алгоритмов, актуальная математика

Введение

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

В 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}
ight
floor , то 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 для некоторого , вернуть СОСТАВНОЕ.
Если вернуть СОСТАВНОЕ.
Для каждого : Если $(x + a)^n e x^n + a pmod{x^r - 1, n}$ вернуть СОСТАВНОЕ.
Вернуть ПРОСТОЕ.

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

Шаг 1

На первом шаге нужно определить, является ли число n точной степенью другого числа, т. е. n = a^b . Пожалуй, самый простой способ сделать это — проверить, что $left lfloor n^{1/b} ight floor^b e 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
ight
floor = 5

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

$left lfloor 47^{1/2} ight floor^2 = 36$

$left lfloor 47^{1/3} ight floor^3 = 27$

$left lfloor 47^{1/4} ight floor^4 = 16$

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

Шаг 2

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

Проверить, что $n^k e 1 pmod{r}$ для всех .
Если одно из значений равно единице — попробовать следующее 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
floor = 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}
ight
floor = 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 e 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}
ight
floor равенств. Каждое равенство включает O(log n) умножений полиномов степени r, у которых коэффициенты порядка . Каждое равенство может быть проверено за $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 гигабайта памяти. Для практического применения лучше всего на данный момент использовать вероятностные алгоритмы.

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

Источник: habr.com



		Полиномиальный алгоритм проверки чисел на простоту: тест Агравала-Каяла-Саксены
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Городские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ Разработка ИИ ИИ теория Компьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Внедрение ИИ Big data Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Работа разума и сознание Изучение сна Изучение сознания Нейроинтерфейс Психология Работа мозга Работа памяти Работа разума Модель мозга Модель мозга Робототехника, БПЛА Беспилотные автомобили БПЛА Робототехника Трансгуманизм Трансгуманизм Обработка текста Анализ социальных сетей Компьютерная лингвистика Лингвистика Поисковые алгоритмы Теория эволюции Головной мозг Нейронные сети Поведение животных Теория эволюции Дополненная реальность Виртулаьная реальность Дополненная реальность Железо Интернет вещей Квантовый компьютер Нейронные процессоры облачные вычисления Суперкомпьютеры Киберугрозы Кибербезопасность Научный мир Методы исследования Наука и образование Семинары ИТ индустрия ИТ-гиганты Новости ит Разработка ПО Разработка ПО Теория алгоритмов Теория информации Кластеризация Математика Актуальная математика Статистика Теория вероятности Теория информации Теория хаоса Цифровая экономика Технология блокчейн Цифровая экономика Авторизация RSS RSS новости		2024-11-08 12:50 Теория алгоритмов, актуальная математика Введение Одной из важнейших задач в теории чисел является проверка числа на простоту. То есть по заданному числу эффективно определить, является оно простым или составным. Алгоритмы, решающие эту задачу (их также называют тестами простоты), известны с древних времён, например решето Эратосфена. Но алгоритма, имеющего полиномиальную сложность, долгое время известно не было. В 2002 году индийскими математиками Агравалом, Кайялом и Саксеной в работе «PRIMES is in P» был впервые предложен алгоритм проверки простоты чисел, который одновременно является полиномиальным, универсальным, детерминированным и безусловным. До этого были известны алгоритмы, которые обладали максимум тремя из четырёх свойств. Полиномиальность означает, что сложность алгоритма ограничена полиномом от количества бит в числе. Примером теста, которые не удовлетворяет свойству полиномиальности, является тест Адлемана-Померанца-Румели. Универсальность подразумевает, что алгоритм применим к любым числам, а не только к числам специального вида. Примером неуниверсального алгоритма является тест Люка-Лемера, который применим только для чисел Мерсенна. Детерминированность означает, что алгоритм всегда выдаёт один и тот же ответ на одних и тех же входных данных. Примером недетерминированного (вероятностного) теста, может служить тест Миллера-Рабина. Безусловность — это независимость от недоказанных гипотез. Не удовлетворяет свойству безусловности, например, тест Миллера, который опирается на обобщённую гипотезу Римана. Обозначения $mathbb {Z}_n$ - кольцо вычетов по модулю n. Запись означает, что многочлены, коэффициенты которых рассматриваются как вычеты из $mathbb {Z}_n$ , равны. Запись $g(x) = h(x) pmod{x^r - 1, n}$ означает, что многочлены с коэффициентами из $mathbb {Z}_n$ равны по модулю многочлена . — порядок числа n по модулю r. Минимальное число k, такое что $n^k = 1 pmod{r}$ . — функция Эйлера. Количество натуральных чисел, меньших n и взаимно простых с ним. — логарифм по основанию два числа n. Основная идея Основная идея алгоритма опирается на следующую теорему: Теорема: Если числа a и n взаимно просты, то тождество $(x + a)^n = x^n + a pmod{n}$ выполняется тогда и только тогда, когда 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}$ Выполнено для всех , то 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 для некоторого , вернуть СОСТАВНОЕ. Если вернуть СОСТАВНОЕ. Для каждого : Если $(x + a)^n e x^n + a pmod{x^r - 1, n}$ вернуть СОСТАВНОЕ. Вернуть ПРОСТОЕ. Рассмотрим подробно реализацию каждого шага алгоритма и разберём выполнение на примере числа 47. Шаг 1 На первом шаге нужно определить, является ли число n точной степенью другого числа, т. е. . Пожалуй, самый простой способ сделать это — проверить, что $left lfloor n^{1/b} ight floor^b e 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: $left lfloor 47^{1/2} ight floor^2 = 36$ $left lfloor 47^{1/3} ight floor^3 = 27$ $left lfloor 47^{1/4} ight floor^4 = 16$ Следовательно, 47 не является точной степенью другого числа. Шаг 2 Подходящее r находится перебором. Для каждого r нужно: Проверить, что $n^k e 1 pmod{r}$ для всех . Если одно из значений равно единице — попробовать следующее r. Если все не равны единице — 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: $47^{1} pmod{41} = 6$ $47^{2} pmod{41} = 36$ $47^{32} pmod{41} = 37$ Шаги 3-4 Элементарные, требуется только реализовать вычисление НОД двух чисел. Шаг 5 Для достижения теоретической сложности достаточно использовать быстрые алгоритмы для арифметических операций с многочленами. Здесь рассмотрим одну эффективную на практике оптимизацию: нахождение остатка от деления без прямого деления многочленов, используя только сложения. Если многочлен степени возводится в квадрат, то в результате получается многочлен степени : $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$ Рассмотрим деление на : , где $a(x) = a_{r-2}x^{r-2} + ldots + a_0$ $b(x) = b_{r-2}x^{r-2} + ldots + b_0$ Раскрывая скобки, находим коэффициенты : $b_1 = c_1 + a_1 = c_1 + c_{1 + r}$ $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; } }` Пример: $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$ $a = 36: (x + 36)^{47} = x^{47} + 36 pmod{x^{41} - 1, 47} = x^6 + 36$ Оценка сложности Введём обозначение: , где — некоторая функция от n. При оценках будем опираться на то, что умножение и деление m-битных чисел имеют сложность . Соответственно, операции над полиномами степени d имеют сложность . НОД двух m-битных чисел можно найти за . На первом шаге определение, является ли число точной степенью, имеет сложность $widetilde{O}(log^3n)$ . На втором шаге нужно найти r. Это делается перебором возможных значений r и проверкой $n^k e 1 pmod{r}$ для всех . Для каждого r это требует умножений по модулю r, значит для каждого r сложность $widetilde{O}(log^2n log r)$ . Учитывая, что r имеет порядок , сложность всего шага равна $widetilde{O}(log^7n)$ . Третий шаг требует вычисления НОД для r чисел. Общая сложность шага . На пятом шаге нужно проверить равенств. Каждое равенство включает умножений полиномов степени r, у которых коэффициенты порядка . Каждое равенство может быть проверено за $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 гигабайта памяти. Для практического применения лучше всего на данный момент использовать вероятностные алгоритмы. Канал с дополнительными материалами. Источник: habr.com Комментарии:

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

Комментарии: