Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест APR) — наиболее[1] эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 году. Назван в честь его исследователей — Леонарда Адлемана, Карла Померанса и Роберта Румели[англ.]. Алгоритм содержит арифметику в цикломатических полях.
Впоследствии алгоритм был улучшен Генри Коэном[англ.] и Хендриком Ленстрой до APR-CL, время работы которого для любого числа
можно вычислить как
, где
— некоторая вычисляемая константа.
До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность
позволяет практическое использование алгоритма.
К примеру, для числа
— гуголплекс,
Старая шутка гласит:
"Доказано, что
стремится к бесконечности, но никто никогда не видел, как он это делает."Иэн Стюарт
Пусть имеется некоторое конечное множество
простых чисел. Если для некоторого простого числа
выполнены следующие условия:
— свободное от квадратов число
- все простые делители
принадлежат множеству ![{\displaystyle {\mathcal {J}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8fb0b896b1b2a45546779ecafc567f4f1688714)
тогда
называется евклидовым простым числом относительно множества
.
Для заданного числа
построим множество
такое, что произведение всех евклидовых простых чисел относительно этого множества будет больше
. Выберем наименьшее возможное
.
Элементы
из этого множества назовем набором «начальных» простых чисел.
Введем некоторое число
. Пусть
— его первообразный корень. Тогда должно выполняться следующее условие:
,
где
.
Замечание: В качестве
выбираем наименьшее неотрицательное число.
Суммой Якоби называют сумму следующего вида:
,
где суммирование идет по всем наборам классов смежности для
в
, кроме тех, что равны
.
Основные леммы[2], используемые при доказательстве корректности алгоритма:
Лемма 2.
Пусть
и имеет порядок
в группе
. Возьмем
. Так же
где
— многочлен в
для каждого
. Будем считать, что идеалы
Если
является простым делителем
, тогда в
:
и каждое
![{\displaystyle (r,{\mathfrak {A}}_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29da1386d9ae302e4bfd2fcf706ca1348e879785)
, делимое на некоторый простой идеал из
![{\displaystyle \mathbf {Z} [\zeta _{q}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/952a46dd352fc6fcfa4131c01a79c07b599468cd)
, лежит над
![{\displaystyle (r)~.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e16c004aef5edfd283c9bee309436d279218808)
Лемма 4.
Если
![{\displaystyle \alpha \equiv 1\mod \lambda ^{i},~\gamma \equiv 1\mod \lambda ^{j},~i+j\geq p+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1431d803c76aad2a5e74f5ce01c23ffa72dea86)
, тогда
![{\displaystyle (\alpha ,\gamma )_{\lambda }=1~.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bb577fcb7701dce9d1a5f725db747def2c28547)
Лемма 5.
Выберем
такие, что
. Для
положим:
то есть
или
.
Тогда
![{\displaystyle J_{a,b}({\mathfrak {L}})=\prod _{u=1}^{p-1}{\sigma _{u}}^{-1}({\mathfrak {A}})^{\theta _{a,b}(u)}~.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f959e572a09a99dac1a3c9798a09690db2ce1a09)
Лемма 6.[3].
Для всех
![{\displaystyle -J_{a,b}({\mathfrak {L}})=1\mod {\lambda }^{2}~.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dea83b3a0d670699ebf4986f0c568802711903bf)
Лемма 7.
Если
, то существуют такие
что
и
![{\displaystyle {\hat {\theta }}_{a,b}\doteq \sum _{u=1}^{p-1}\theta _{a,b}(u)\cdot u^{-1}\not \equiv 0~\mod ~p~,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/981313513e8bf4a38c28166e05e25321d5537ec7)
где
![{\displaystyle u^{-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4bafc86c3426745a84a6074675a2f8bbee9ed76)
— обратный элемент к
![{\displaystyle u\mod p~.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d88c9953a65b5b4d2bcb981737708da150c5f99)
Лемма (Извлечения).
Пусть
— идеалы в
такие, что
и пусть
сопряженные простые идеалы, делящие
соответственно. Пускай существует такое
что
. Тогда для любого
выполняется:
и следовательно
Если
является составным числом, то оно имеет некий делитель
. Для проверки на простоту ищем это
.
Если нам известны значения
для каждой пары
, то по китайской теореме об остатках мы можем найти
. Каждая пара
выбирается следующим образом:
, а
— простое евклидово число относительно
такое, что
В алгоритме перебираются все возможные значения
для всех
, исходя из того, что известно только одно
- Ввод: целое число n > 1.
1. Вычисляем наименьшее положительное число
свободное от квадратов, такое что:
.
Определим множество «начальных» простых чисел, являющиеся делителями
. Назовем
евклидовым простым числом, если
простое и
2. Проверим — делится ли
на любое «начальное» или евклидово простое число. Если делитель найдется, причем не равный
, то объявляем
составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень
для каждого евклидового простого числа
.
3. Для каждого «начального» простого числа
найдем числа
такие, что:
,
,
Для
примем
.
4. Для каждого «начального» и евклидового простых чисел, таких что
зафиксируем простой идеал:
,
где
принадлежит
,а
— корень из единицы.
Вычислим сумму Якоби
если
,
если
1. Для каждого «начального» простого числа
найдем НОД в
для
и набора
, где
пробегает все значения евклидовых простых чисел, причем
, а
пробегает по всем значениям из Gal
. Тогда либо выносим решение о том, что
составное, либо строим надлежащий идеал
в кольце
, а также находим числа
и
,
такие, что:
,
или некоторое из
, где
2. Для каждого «начального» простого числа
сделаем следующее: если для некоторого
, тогда возьмем
. В этом ключе построим числа
для всех
,
и такие, что:
Если же для всех
, примем
.
Проделаем шаги 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.