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

Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест 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)bpJa,b=(xL)ap(1xL)bp,
 где суммирование идет по всем наборам классов смежности для xx в Z[ζq]/LZ[ζq]/L, кроме тех, что равны 0,1modL0,1modL.

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


 Основные леммы, используемые при доказательстве корректности алгоритма:
 Простые идеалы из Z[ζq]Z[ζq], лежащие над главным идеалом (q)(q) это: Li=(q,hi(ζq))Li=(q,hi(ζq)) для всех i=1..g.i=1..g.
 Пусть n2n2 и имеет порядок ff в группе (Z/p)(Z/p). Возьмем g=(p1)/fg=(p1)/f. Так же Φp(x)gi=1hi(x)modn,Φp(x)gi=1hi(x)modn, где hi(x)hi(x) — многочлен в Z[x]Z[x] для каждого ff. Будем считать, что идеалы Ai=(n,hi(ζq)).Ai=(n,hi(ζq)). Если rr является простым делителем nn, тогда в Z[ζq]Z[ζq]: (r)=gi=1(r,Ai),(r)=gi=1(r,Ai), и каждое (r,Ai)(r,Ai), делимое на некоторый простой идеал из Z[ζq]Z[ζq], лежит над (r).(r).
 Возьмем p>2p>2 и элементы α,γQ(ζq)α,γQ(ζq) взаимно простые с λλ и относительно друг друга. (αγ)p=(γα)p(α,γ)λ.(αγ)p=(γα)p(α,γ)λ.
(,)λ(,)λ — символ Гильберта.
 Если α1modλi,γ1modλj,i+jp+1α1modλi,γ1modλj,i+jp+1, тогда (α,γ)λ=1.(α,γ)λ=1.
 Выберем a,bZa,bZ такие, что ab(a+b)0modpab(a+b)≢0modp. Для uZuZ положим: θa,b(u)=[a+bpu][apu][bpu],θa,b(u)=[a+bpu][apu][bpu], то есть θa,b(u)=0θa,b(u)=0 или 11. Тогда Ja,b(L)=p1u=1σu1(A)θa,b(u).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.