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

Тест Адлемана-Померанса-Румели (илиАдлемана-Померанца-Румели, тест APR) — наиболее эффективный,детерминированный и безусловный на сегодняшний день тест простоты чисел,разработанный в 1983 году. Назван в честь его исследователей —Леонарда Адлемана, Карла Померанса и Роберта Румели. Алгоритм содержитарифметику в цикломатических полях.
 Впоследствии алгоритм был улучшен Эндри Коэном и Хендриком Ленстрой доAPR-CL, время работы которого для любого числа nn можновычислить как O((lnn)clnlnlnn)O((lnn)clnlnlnn), где cc — некотораявычисляемая константа.

История


 До 1980 года у всех известных алгоритмов проверки на простоту, заисключением вероятностных и недоказанных, временная сложность алгоритмабыла экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащийвблизи P-класса. Технически алгоритм не относится к этомуклассу, однако медленно растущая сложностьO((lnn)clnlnlnn)O((lnn)clnlnlnn) позволяет практическое использованиеалгоритма.
 К примеру, для числа nn — гуголплекс, lnlnlnn5.43lnlnlnn5.43

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


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


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

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

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

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


 Для заданного числа nn построим множество J=J(n)J=J(n)такое, что произведение всех Евклидовых простых чисел относительно этогомножества будет больше nn. Выберем наименьшее возможноеJ(n)J(n).
 Элементы pp из этого множества назовем набором «начальных» простыхчисел.

Indq

(x)
 Введем некоторое число Indq=Indq(x)Indq=Indq(x). Пусть tqtq — егопервообразный корень. Тогда должно выполняться следующее условие:
xtqIndq(x)modqxtqIndq(x)modq,
 где (x,q)=1(x,q)=1.
Замечание: В качестве Indq(x)Indq(x) выбираем наименьшеенеотрицательное число.

СуммаЯкоби


 Суммой Якоби называют сумму следующего вида:
Ja,b=(xL)ap(1xL)bp,
 где суммирование идет по всем наборам классов смежности для x вZ[ζq]/L, кроме тех, что равны0,1modL.

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


 Основные леммы, используемые при доказательстве корректности алгоритма:
 Простые идеалы из Z[ζq], лежащие над главным идеалом(q) это: Li=(q,hi(ζq)) для всех i=1..g.
 Пусть n2 и имеет порядок f в группе (Z/p).Возьмем g=(p1)/f. Так жеΦp(x)gi=1hi(x)modn, где hi(x) —многочлен в Z[x] для каждого f. Будем считать, что идеалыAi=(n,hi(ζq)). Если r является простымделителем n, тогда в Z[ζq]:(r)=gi=1(r,Ai), и каждое(r,Ai), делимое на некоторый простой идеал изZ[ζq], лежит над (r).
 Возьмем p>2 и элементы α,γQ(ζq)взаимно простые с λ и относительно друг друга.(αγ)p=(γα)p(α,γ)λ.
(,)λ — символ Гильберта.
 Еслиα1modλi,γ1modλj,i+jp+1,тогда (α,γ)λ=1.
 Выберем a,bZ такие, что ab(a+b)0modp.Для uZ положим:θa,b(u)=[a+bpu][apu][bpu],то есть θa,b(u)=0 или 1. ТогдаJa,b(L)=p1u=1σu1(A)θa,b(u).
.
 Для всех a,bZ:Ja,b(L)=1modλ2.
 Если p>2, то существуют такие a,bZ, чтоab(a+b)0modp иˆθa,bp1u=1θa,b(u)u10modp,где u1 — обратный элемент к umodp.
 Пусть A,A1 — идеалы в Z[ζq]такие, что pNA=NA1 и пустьR,R1 сопряженные простые идеалы, делящиеA,A1 соответственно. Пускай существует такоеγZ[ζq], чтоγAp0,1.Тогда для любого α1Z[ζq] выполняется:
γAmp=α1A1p
 и следовательно
γRmp=α1R1p.

Идеяалгоритма


 Если n является составным числом, то оно имеет некий делитель r. Дляпроверки на простоту ищем это r1,rn.
 Если нам известны значения Indq(r)modp для каждой пары p,q, топо китайской теореме об остатках мы можем найти r. Каждая пара p,qвыбирается следующим образом: pJ(n), а q — простоеЕвклидово число относительно J(n) такое, что p|q1.
 В алгоритме перебираются все возможные значения Indq(r)modp длявсех q, исходя из того, что известно только одно q.

Алгоритм



 Ввод: целое число n \textgreater 1.

agraphA. Шагподготовки
1. Вычисляем наименьшее положительное число f(n) свободное отквадратов, такое что: qprimeq1|f(n)q>n.
 Определим множество «начальных» простых чисел, являющиеся делителямиf(n). Назовем q Евклидовым простым числом, если q простое иq1|f(n)
2. Проверим — делится ли n на любое «начальное» илиЕвклидово простое число. Если делитель найдется, причем не равный n.Тогда объявляем n составным и прерываем алгоритм. Иначе вычислимнаименьший положительный первообразный корень tq для каждогоЕвклидового простого числа q.
3. Для каждого «начального» простого числа p>2 найдем числаa,b такие, что:
0<a,b<p,
a+b0modp,
ˆθa,b=p1u=1θa,b(u)u10modp.
 Для p=2 примем a=b=ˆθa,b=1.
4. Для каждого «начального» и Евклидового простых чисел, такихчто p|q1 зафиксируем простой идеал:
Lq=(q,ζqt(q1)/pq),
 где q принадлежит Z[ζq]ζq=e2πi/p —корень из единицы.
 Вычислим сумму Якоби Jp(q)Q(ζq):
 если p=2:Jp(q)=q,
 еслиp>2:Jp(q)=Ja,b(Lq)=q1x=2(xLq)ap(1xLq)bp.

agraphB. Шагвычислений
1. Для каждого «начального» простого числа p найдем НОД вQ(ζq) для n и набора σJp(q), где qпробегает все значения Евклидовых простых чисел, причем p|q1, аσ пробегает по всем значениям изGal(Q(ζq)/Q). Тогда либо выносим решение отом, что n составное, либо строим надлежащий идеал A вкольце Z[ζq], а также находим числа s и j(σ,q),1j(σ,q)p такие, что:
(σJp(q))(nf1)/psζqj(σ,q)modA,
p(nf1)/ps или некоторое изζqj(σ,q)1, где f=nmodp.
2. Для каждого «начального» простого числа p сделаемследующее: если для некоторого j(σ0,q0)p, тогда возьмемγ=σ0Jp(q0). В этом ключе построим числа m(σ,q)для всех σ,q, 0m(σ,q)p1 и такие, что:
(γ(nf1)/ps)m(σ,q)(σJp(q))(nf1)/psmodA.
 Если же для всех j(σ,q)=p, примем m(σ,q)=0.

agraphC. Шаг объединениярезультатов
 Проделаем шаги 1-4 для всех натуральных k,1kf(n).
1. Для каждого q>2 вычислим по китайской теореме об остаткахвычислим числа I(k,q):
I(k,q)=kˆθa,b1p1j=1jm(σj1,q)modp,
 при всевозможных p, что p|q1. Так же положим, что I(k,2)=1.
2. Для каждого q посчитаем наименьшее целое, положительноечисло r(k,q)tqI(k,q)modq.
3. Используя Китайскую теорему об остатках, вычислим наименьшееположительное число r(k) такое, что r(k)r(k,q)modq длякаждого q.
4. Если r(k)1,r(k)n,r(k)|n, тогда объявляем nсоставным. Иначе переходим к следующему k.
5. Объявляем n простым.

Оценкасложности


 Оценка времени выполнения алгоритма вытекает из следующих теорем:
 Для значений n>1 вышеупомянутый алгоритм правильно определяет будет лиn простым или составным за время T(n). И справедливы следующиеоценки: f(n)T(n), для простых n, T(n)fc1(n), длявсех значения n. Где c1 — положительная, вычисляемая константа.
 Существуют такие положительные, вычисляемые константы c2,c3, чтодля всех n>100:(ln(n))c2lnlnln(n)<f(n)<(ln(n))c3lnlnln(n)

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



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