Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест APR) — наиболее эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 году. Назван в честь его исследователей — Леонарда Адлемана, Карла Померанса и . Алгоритм содержит арифметику в цикломатических полях.
Впоследствии алгоритм был улучшен и Хендриком Ленстрой до APR-CL, время работы которого для любого числа можно вычислить как , где — некоторая вычисляемая константа.
История До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность позволяет практическое использование алгоритма.
К примеру, для числа — гуголплекс,
Ключевые понятия
Евклидово простое число Пусть имеется некоторое конечное множество простых чисел. Если для некоторого простого числа выполнены следующие условия:
— свободное от квадратов число все простые делители принадлежат множеству
тогда называется евклидовым простым числом относительно множества .
Набор «начальных» простых чисел Для заданного числа построим множество такое, что произведение всех евклидовых простых чисел относительно этого множества будет больше . Выберем наименьшее возможное .
Элементы из этого множества назовем набором «начальных» простых чисел.
Indq(x) Введем некоторое число . Пусть — его первообразный корень. Тогда должно выполняться следующее условие:
,
где .
Замечание: В качестве выбираем наименьшее неотрицательное число.
Сумма Якоби Суммой Якоби называют сумму следующего вида:
,
где суммирование идет по всем наборам классов смежности для в , кроме тех, что равны .
Ключевые леммы Основные леммы, используемые при доказательстве корректности алгоритма:
Простые идеалы из , лежащие над главным идеалом это: для всех
Пусть и имеет порядок в группе . Возьмем . Так же
где — многочлен в для каждого . Будем считать, что идеалы Если является простым делителем , тогда в :
и каждое , делимое на некоторый простой идеал из , лежит над
Возьмем и элементы взаимно простые с и относительно друг друга.
— символ Гильберта.
Если , тогда
Выберем такие, что . Для положим:
то есть или . Тогда
.
Для всех
Если , то существуют такие что и где — обратный элемент к
Пусть — идеалы в такие, что и пусть сопряженные простые идеалы, делящие соответственно. Пускай существует такое что . Тогда для любого выполняется:
и следовательно
Идея алгоритма Если является составным числом, то оно имеет некий делитель . Для проверки на простоту ищем это .
Если нам известны значения для каждой пары , то по китайской теореме об остатках мы можем найти . Каждая пара выбирается следующим образом: , а — простое евклидово число относительно такое, что
В алгоритме перебираются все возможные значения для всех , исходя из того, что известно только одно
Алгоритм Ввод: целое число n > 1.
A. Шаг подготовки 1. Вычисляем наименьшее положительное число свободное от квадратов, такое что: .
Определим множество «начальных» простых чисел, являющиеся делителями . Назовем евклидовым простым числом, если простое и
2. Проверим — делится ли на любое «начальное» или евклидово простое число. Если делитель найдется, причем не равный , то объявляем составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень для каждого евклидового простого числа .
3. Для каждого «начального» простого числа найдем числа такие, что:
,
,
Для примем .
4. Для каждого «начального» и евклидового простых чисел, таких что зафиксируем простой идеал:
,
где принадлежит ,а — корень из единицы.
Вычислим сумму Якоби
если ,
если
B. Шаг вычислений 1. Для каждого «начального» простого числа найдем НОД в для и набора , где пробегает все значения евклидовых простых чисел, причем , а пробегает по всем значениям из Gal. Тогда либо выносим решение о том, что составное, либо строим надлежащий идеал в кольце , а также находим числа и , такие, что:
,
или некоторое из , где
2. Для каждого «начального» простого числа сделаем следующее: если для некоторого , тогда возьмем . В этом ключе построим числа для всех , и такие, что:
Если же для всех , примем .
C. Шаг объединения результатов Проделаем шаги 1-4 для всех натуральных
1. Для каждого вычислим по китайской теореме об остатках вычислим числа :
при всевозможных , что . Так же положим, что
2. Для каждого посчитаем наименьшее целое, положительное число
3. Используя Китайскую теорему об остатках, вычислим наименьшее положительное число такое, что для каждого
4. Если , тогда объявляем составным. Иначе переходим к следующему
5. Объявляем простым.
Оценка сложности Оценка времени выполнения алгоритма вытекает из следующих теорем:
Для значений вышеупомянутый алгоритм правильно определяет будет ли простым или составным за время . И справедливы следующие оценки: для простых для всех значения Где — положительная, вычисляемая константа.
Существуют такие положительные, вычисляемые константы , что для всех
Программная реализация В приведена реализация алгоритма под именем APRT-CLE (APR Test CL extended) factoring applet использует алгоритм APR-CL с определёнными условиями Pari/GP условное использование APR-CL в реализации isprime(). mpz_aprcl реализация с открытым исходным кодом. Использует C + GMP.
Примечания
Список литературы
Категория:Тесты простоты Категория:Теория чисел