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

Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест APR) — наиболее[1] эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 году. Назван в честь его исследователей — Леонарда Адлемана, Карла Померанса и Роберта Румели. Алгоритм содержит арифметику в цикломатических полях.

Впоследствии алгоритм был улучшен Генри Коэном и Хендриком Ленстрой до APR-CL, время работы которого для любого числа можно вычислить как , где  — некоторая вычисляемая константа.

История

До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность позволяет практическое использование алгоритма.

К примеру, для числа  — гуголплекс,

Старая шутка гласит:
"Доказано, что стремится к бесконечности, но никто никогда не видел, как он это делает."Иэн Стюарт

Ключевые понятия

Евклидово простое число

Пусть имеется некоторое конечное множество простых чисел. Если для некоторого простого числа выполнены следующие условия:

  1.  — свободное от квадратов число
  2. все простые делители принадлежат множеству

тогда называется Евклидовым простым числом относительно множества .

Набор «начальных» простых чисел

Для заданного числа построим множество такое, что произведение всех Евклидовых простых чисел относительно этого множества будет больше . Выберем наименьшее возможное .

Элементы из этого множества назовем набором «начальных» простых чисел.

Indq(x)

Введем некоторое число . Пусть  — его первообразный корень. Тогда должно выполняться следующее условие:

,

где .

Замечание: В качестве выбираем наименьшее неотрицательное число.

Сумма Якоби

Суммой Якоби называют сумму следующего вида:

,

где суммирование идет по всем наборам классов смежности для в , кроме тех, что равны .

Ключевые леммы

Основные леммы[2], используемые при доказательстве корректности алгоритма:

Лемма 1.

Простые идеалы из , лежащие над главным идеалом это:

для всех
Лемма 2.

Пусть и имеет порядок в группе . Возьмем . Так же где  — многочлен в для каждого . Будем считать, что идеалы Если является простым делителем , тогда в :

и каждое , делимое на некоторый простой идеал из , лежит над
Лемма 3.

Возьмем и элементы взаимно простые с и относительно друг друга.

 — символ Гильберта.

Лемма 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]:

Теорема 1.

Для значений вышеупомянутый алгоритм правильно определяет будет ли простым или составным за время . И справедливы следующие оценки: для простых

для всех значения Где  — положительная, вычисляемая константа.
Теорема 2.

Существуют такие положительные, вычисляемые константы , что для всех

Программная реализация

  • В UBASIC приведена реализация алгоритма под именем APRT-CLE (APR Test CL extended)
  • factoring applet использует алгоритм APR-CL с определёнными условиями
  • Pari/GP условное использование APR-CL в реализации isprime().
  • mpz_aprcl реализация с открытым исходным кодом. Использует C + GMP.

Примечания

  1. Стюарт, 2015.
  2. Adleman, Pomerance, Rumely, 1983.
  3. K. Iwasawa. A note on jacobi sum (англ.) // Symposia Math. — 1975. С. 447—459.

Список литературы

  • Иэн Стюарт. Величайшие математические задачи. М.: Альпина нон-фикшн, 2015. — 460 с. — ISBN 978-5-91671-318-3.
  • Leonard M. Adleman, Carl Pomerance and Robert S. Rumely.  (англ.) = On distinguishing prime numbers from composite numbers. — 1983. P. 7—25.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.