Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест APR) — наиболее[1] эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 году. Назван в честь его исследователей — Леонарда Адлемана, Карла Померанса и Роберта Румели[англ.]. Алгоритм содержит арифметику в цикломатических полях.
Впоследствии алгоритм был улучшен Генри Коэном[англ.] и Хендриком Ленстрой до APR-CL, время работы которого для любого числа можно вычислить как , где — некоторая вычисляемая константа.
История
До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность позволяет практическое использование алгоритма.
К примеру, для числа — гуголплекс,
Старая шутка гласит:
"Доказано, что стремится к бесконечности, но никто никогда не видел, как он это делает."Иэн Стюарт
Ключевые понятия
Евклидово простое число
Пусть имеется некоторое конечное множество простых чисел. Если для некоторого простого числа выполнены следующие условия:
- — свободное от квадратов число
- все простые делители принадлежат множеству
тогда называется евклидовым простым числом относительно множества .
Набор «начальных» простых чисел
Для заданного числа построим множество такое, что произведение всех евклидовых простых чисел относительно этого множества будет больше . Выберем наименьшее возможное .
Элементы из этого множества назовем набором «начальных» простых чисел.
Indq(x)
Введем некоторое число . Пусть — его первообразный корень. Тогда должно выполняться следующее условие:
,
где .
Замечание: В качестве выбираем наименьшее неотрицательное число.
Сумма Якоби
Суммой Якоби называют сумму следующего вида:
,
где суммирование идет по всем наборам классов смежности для в , кроме тех, что равны .
Ключевые леммы
Основные леммы[2], используемые при доказательстве корректности алгоритма:
Лемма 2.Пусть и имеет порядок в группе . Возьмем . Так же где — многочлен в для каждого . Будем считать, что идеалы Если является простым делителем , тогда в :
и каждое
, делимое на некоторый простой идеал из
, лежит над
Лемма 4. Если
, тогда
Лемма 5.Выберем такие, что . Для положим: то есть или .
Тогда
Лемма 6.[3].Для всех
Лемма 7.Если , то существуют такие что и
где
— обратный элемент к
Лемма (Извлечения).
Пусть — идеалы в такие, что и пусть сопряженные простые идеалы, делящие соответственно. Пускай существует такое что . Тогда для любого выполняется:
и следовательно
Идея алгоритма
Если является составным числом, то оно имеет некий делитель . Для проверки на простоту ищем это .
Если нам известны значения для каждой пары , то по китайской теореме об остатках мы можем найти . Каждая пара выбирается следующим образом: , а — простое евклидово число относительно такое, что
В алгоритме перебираются все возможные значения для всех , исходя из того, что известно только одно
Алгоритм
- Ввод: целое число n > 1.
A. Шаг подготовки
1. Вычисляем наименьшее положительное число свободное от квадратов, такое что: .
Определим множество «начальных» простых чисел, являющиеся делителями . Назовем евклидовым простым числом, если простое и
2. Проверим — делится ли на любое «начальное» или евклидово простое число. Если делитель найдется, причем не равный , то объявляем составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень для каждого евклидового простого числа .
3. Для каждого «начального» простого числа найдем числа такие, что:
,
,
Для примем .
4. Для каждого «начального» и евклидового простых чисел, таких что зафиксируем простой идеал:
,
где принадлежит ,а — корень из единицы.
Вычислим сумму Якоби
если ,
если
B. Шаг вычислений
1. Для каждого «начального» простого числа найдем НОД в для и набора , где пробегает все значения евклидовых простых чисел, причем , а пробегает по всем значениям из Gal. Тогда либо выносим решение о том, что составное, либо строим надлежащий идеал в кольце , а также находим числа и , такие, что:
,
или некоторое из , где
2. Для каждого «начального» простого числа сделаем следующее: если для некоторого , тогда возьмем . В этом ключе построим числа для всех , и такие, что:
Если же для всех , примем .
C. Шаг объединения результатов
Проделаем шаги 1-4 для всех натуральных
1. Для каждого вычислим по китайской теореме об остатках вычислим числа :
при всевозможных , что . Так же положим, что
2. Для каждого посчитаем наименьшее целое, положительное число
3. Используя Китайскую теорему об остатках, вычислим наименьшее положительное число такое, что для каждого
4. Если , тогда объявляем составным. Иначе переходим к следующему
5. Объявляем простым.
Оценка сложности
Оценка времени выполнения алгоритма вытекает из следующих теорем[2]:
Программная реализация
Примечания
Список литературы
- Иэн Стюарт. Величайшие математические задачи. — М.: Альпина нон-фикшн, 2015. — 460 с. — ISBN 978-5-91671-318-3.
- Leonard M. Adleman, Carl Pomerance and Robert S. Rumely. [1] (англ.) = On distinguishing prime numbers from composite numbers. — 1983. — P. 7—25.