blog.iakovlev.org
  20.01.2016

Тест Адлемана — Померанса — Румели

Тест Адлемана-Померанса-Румели (APR) — эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 г. Назван в честь его исследователей- Леонарда Адлемана, Карла Померанса и Роберта Румели.
Детерминированный тест имеет принципиальное отличие от вероятностных тестов, к каковым относится например тест Миллера-Рабина. Детерминированный тест гарантированно, т.е. на 100% гарантии, определяет, является число простым или составным. Время работы такого теста может быть существенно больше времени работы вероятностных тестов, особенно при возрастании разрядности проверяемых чисел.
Впоследствии алгоритм был улучшен Эндри Коэном и Хендриком Ленстрой до APR-CL, время работы которого для любого числа n можно вычислить как
O((ln(n))c*ln(ln(ln(n))))

Большинство современных алгоритмов проверки чисел на простоту основано на малой теореме Ферма (формула 1):

При этом существуют две основных проблемы.
Первая проблема: оказывается, что число n может отвечать данному сравнению и быть при этом составным, а не простым числом, например:
561 = 3*11*17
Такие числа называются числами кармайкла, и их скорее всего бесконечно много. Т.е. малая теорема Ферма является необходимым, но недостаточным условием для простоты числа.
Вторая проблема заключается в том, что при увеличении n время перебора чисел a по модулю n стремится к бесконечности.

Для решения первой проблемы есть два варианта.
В первом варианте используются символы Якоби вида (a/n), где a - число, взаимно простое с n. Если n - число простое, то должно выполняться условие (формула 2):

Во втором варианте используется еще одна интерпретация все той же малой теоремы Ферма - для простых n должно выполняться условие(формула 3):
(a + b)n ≡ an + bn (mod n)

Проблема времени остается актуальной как для первой, так и для второй и для третьей формулы. Для ее решения в APR выбирается и проверяется ограниченная группа возможных делителей числа n и на основе анализа делается вывод о наличии делителей у числа n вообще.

Прежде чем перейти к рассмотрению самого алгоритма APR. нужно определить некоторые базовые обьекты, которые будут там использоваться. Речь пойдет о символе Лежанжра, символе Дирихле, символе Якоби, первообразном корне.

Символ Лежандра

Символ Лежандра — функция, используемая в теории чисел. Введён французским математиком А. М. Лежандром. Пусть a — целое число, и p — простое число, отличное от 2. Символ Лежандра обозначается как

Символ Лежандра может принимать три значения: 0, 1, -1.
Символ Лежандра равен 0,если a делится на p:

Символ Лежандра равен 1, если a является квадратичным вычетом по модулю p,

то есть a не делится на p и существует такое целое x, что

В остальных случаях символ Лежандра равен -1:

Для символа Лежандра справедлива формула Эйлера:

Следующий код вычисляет символ Лежандра:
Код


Символ Дирихле

Символ Дирихле (или характер Дирихле или просто характер) по модулю k, где k>2 - периодическая функция χ(n), принимающая два значения - 0 либо 1. Если n и k взаимно простые,

В противном случае

Существует в точности φ (k) различных характеров по модулю k, где φ(k) — функция Эйлера.

Символ Якоби

Символ Якоби — теоретико-числовая функция двух аргументов, обобщает символ Лежандра на все нечётные числа, большие единицы.
Пусть P — нечётное, большее единицы число и P=p1p2...pn — его разложение на простые множители. Тогда для произвольного целого числа a символ Якоби определяется равенством:

Символ Якоби имеет значение только для нечетных p. Если p - простое число, символ якобы эквивалентен вычислению символа Лежандра.
Следующий код вычисляет символ Якоби:
Код

Первообразный корень

Первообразный корень по модулю m ― целое число g такое, что

и

где φ(m) - функция Эйлера, и 1 < l < φ(m).
Первообразные корни существуют только для чисел вида 2, 4, pa, 2pa, где p - простое число.
Для каждого числа a, взаимно простого с m, найдется показатель ℓ, 0 ⩽ ℓ ⩽ φ(m) − 1, такой, что

Такое число ℓ называется индексом числа a по основанию g.
Если по модулю m существует первообразный корень g, то всего существует φ(φ(m)) различных первообразных корней по модулю m.
Пример: пусть m=13. φ(13)=12. φ(φ(13))=φ(12)=4. Т.е. у числа 13 - четыре первообразных корня: 2, 6, 7, 8.
Следующий код вычисляет первообразный корень:
Код

Китайская теорема об остатках.

Эта теорема была доказана еще в 13 веке. Сейчас она звучит так:
Если натуральные числа a1,a2,...,an, попарно взаимно просты, то для любых целых r1,r2,...,rn, таких, что 0 < ri < ai при всех i = {1, 2,..., n}, найдётся число N, которое при делении на a1 даёт остаток r1 при всех i = {1, 2,..., n}. Более того, если найдутся два таких числа N1 и N2, то N1 ≡ N1 (mod a1*a2...*an).

Пример: Нужно вычислить число x, для которого есть набор из трех остатков от деления на три взаимно простых числа:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 6 (mod 7)

Для решения системы выпишем отдельно решения первого, второго и третьего уравнений (достаточно выписать решения не превосходящие 2 × 3 × 7 = 42):
x1 = {1,3,5,7,9,...,39,41,43, ...}
x2 = {2,5,8,11,14,...,38,41,44, ...}
x3 = {6,13,20,27,34,...,41,48, ...}
Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю 42. В нашем случае x = {41, 83, 125, ...} или
x ≡ 41 (mod 42)
Следующий код решает данный пример:
Код


Реализация APR

Перейдем непосредственно к самому алгоритму APR.
Мы выбираем для проверки на простоту число n.
Вначале нужно вычислить функцию e(t), где t - четное число в диапазоне: 2,4,6,8,10,...
Функция вычисляется по следующему алгоритму:

Берется каноническое разложение числа t. e(t) является функцией от простых чисел, входящих в разложение числа t. В этой формуле числа q - это числа, входящие в каноническое разложение числа t, vq - это показатель степени, с которым число q входит в это разложение.
Функция e(t) принимает следующие значения для нескольких первых t:
te(t)
224
4240
6504
1265520
24131040
30171864
36138181680
606814407600
7220174525280
......
504015321986788854443284662612735663611380010431225771200
......
Из этой таблицы нужно выбрать такое минимальное e(t), для которого выполняется неравенство:
e(t) > n1/2
Например, e(5040) подходит для проверки любого числа, чиcло разрядов которого не превышает 100 цифр, т.е. 10100
Каноническое разложение числа e(5040) выглядит так:
e(5040) = 26 * 33 * 52 * 72 * 11 * 13 * 17 * 19 * 29 * 31 * 37 * 41 * 43 * 61 * 71 * 73 * 113 * 127 * 181 * 211 * 241 * 281 * 337 * 421 * 631 * 1009 * 2521
Каждое число в этом разложении обозначается как q, оно может иметь степень, большую или равную единице. Каждому такому числу q ставится в соответствие число, меньшее на единицу, т.е. q-1, и для каждого такого числа q-1 вычисляется свое собственное каноническое разложение , которое затем будет применяться в тесте APR.

Тест APR - композитный тест. Он состоит из нескольких более мелких вложенных тестов. Каждый такой вложенный тест определяет по какому-то своему алгоритму простоту числа n. Если число n проходит все эти тесты, то оно гарантированно - простое число.

Первый тест ищет НОД для двух чисел - для n и для t * e(t). Если НОД не равен единице, то n - число составное, и тест заканчивается.

Второй тест является вероятностным тестом. В его основе лежит все та же малая теорема Ферма.
Пусть n - 1 = u * 2k, где k < m, m=6. Чтобы доказать, что число n - составное, выбирается случайное число a, меньшее n, и для такого числа ищем выполнение хотя бы одно из двух условий:
1. НОД для чисел au и n не равняется 1
2. НОД для чисел au*2i и n не равняется 1, где i < m
Здесь число u лежит в диапазоне от 1 до 2m-1

Основной алгоритм APR постороен на основе вычисления т.н. сумм Якоби.
Сначала мы берем - в качестве примера - e(5040) и его каноническое разложение в виде массива простых чисел q :
q = [2,3,5,7,11,13,17,19,29,31,37,41,43,61,71,73,113,127,181,211,241,281,337,421,631,1009,2521]
Этого достаточно, чтобы проверить на простоту любое 100-значное число.
Для каждого простого числа q в этом массиве ставится в соответствие число q-1, для которого в свою очередь вычисляется каноническое разложение чисел, которые обозначим символом p. Для каждой пары p, q вычисляется первообразный корень по модулю q. Далее вычисляем числовой характер по модулю q порядка p. Далее вычисляем сумму Якоби :

Для каждого начального простого числа p находим наибольшее натуральное число h = h(p), 1 < h < t = νp*(np−1 − 1), такое, что для всех q таких, что p | q − 1, выполнено сравнение (1.2)

Здесь ξp,q - некоторый корень степени p из единицы. αh(n) - некоторый явно определяемый по n элемент группового кольца Z[Gal(Q(ζp))].
Если

то

Мы работаем с целочисленными векторами размерности p-1. Сравнение (1.2) означает, что координаты двух таких векторов сравнимы по модулю n.
Если сравнение (1.2) не выполнено при некоторых p, q, h=1 и

то n - составное число.

Более полное описание алгоритма можно найти в статье авторов самого теста.
Существует несколько открытых реализаций теста apr.
Питоновская реализация apr сделана в проекте nzmath, который можно скачать с SourceForge
Следующий код взят из этого проекта. 100-значное простое число на стандартном персональном компьютере проверяется примерно за 20 секунд.
Код





 Автор   Комментарий к данному блогу
Комментарий

Ваше имя:
Комментарий:
Оба поля являются обязательными