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

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

Впоследствии алгоритм был улучшен Шаблон:Iw и Хендриком Ленстрой до APR-CL, время работы которого для любого числа $n$ можно вычислить как $O((\ln n{)}^{c\ln \ln \ln n})$, где $c$ — некоторая вычисляемая константа.

История

До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность $O((\ln n{)}^{c\ln \ln \ln n})$ позволяет практическое использование алгоритма.

К примеру, для числа $n$ — гуголплекс, $\ln \ln \ln n\approx 5,44282$

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

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

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

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

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

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

Для заданного числа $n$ построим множество $𝒥=𝒥(n)$ такое, что произведение всех евклидовых простых чисел относительно этого множества будет больше $\sqrt{n}$. Выберем наименьшее возможное $𝒥(n)$.

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

Ind_q(x)

Введем некоторое число $In{d}_q=In{d}_q(x)$. Пусть $t_q$ — его первообразный корень. Тогда должно выполняться следующее условие:

$x\equiv {t_q}^{In{d}_q(x)}modq$,

где $(x,q)=1$.

Замечание: В качестве $In{d}_q(x)$ выбираем наименьшее неотрицательное число.

Сумма Якоби

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

$J_{a,b}=\sum {\left(\frac{x}{𝔏}\right)}_p^{-a}{\left(\frac{1-x}{𝔏}\right)}_p^{-b}$,

где суммирование идет по всем наборам классов смежности для $x$ в $𝐙[{\zeta }_q]/𝔏$, кроме тех, что равны $0,1mod𝔏$.

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

Основные леммыШаблон:Sfn, используемые при доказательстве корректности алгоритма:

Простые идеалы из $𝐙[{\zeta }_q]$, лежащие над главным идеалом $(q)$ это: ${𝔏}_i=(q,h_i({\zeta }_q))$ для всех $i=1..g.$ Шаблон:/lemma

Пусть $n\ge 2$ и имеет порядок $f$ в группе $(𝐙/p{)}^{*}$. Возьмем $g=(p-1)/f$. Так же ${\mathrm{\Phi }}_p(x)\equiv \prod _{i=1}^g{h}_i(x)modn,$ где $h_i(x)$ — многочлен в $𝐙[x]$ для каждого $f$. Будем считать, что идеалы ${𝔄}_i=(n,h_i({\zeta }_q)).$ Если $r$ является простым делителем $n$, тогда в $𝐙[{\zeta }_q]$: $(r)=\prod _{i=1}^g(r,{𝔄}_i),$ и каждое $(r,{𝔄}_i)$, делимое на некоторый простой идеал из $𝐙[{\zeta }_q]$, лежит над $(r).$Шаблон:/lemma

Возьмем $p>2$ и элементы $\alpha ,\gamma \in 𝐐({\zeta }_q)$ взаимно простые с $\lambda$ и относительно друг друга. ${\left(\frac{\alpha }{\gamma }\right)}_p={\left(\frac{\gamma }{\alpha }\right)}_p(\alpha ,\gamma {)}_{\lambda }.$

$(\cdot ,\cdot {)}_{\lambda }$ — символ Гильберта. Шаблон:/lemma

Если $\alpha \equiv 1mod{\lambda }^i,\gamma \equiv 1mod{\lambda }^j,i+j\ge p+1$, тогда $(\alpha ,\gamma {)}_{\lambda }=1.$Шаблон:/lemma

Выберем $a,b\in 𝐙$ такие, что $ab(a+b)\equiv ̸0modp$. Для $u\in 𝐙$ положим: ${\theta }_{a,b}(u)=\left[\frac{a+b}{p}u\right]-\left[\frac{a}{p}u\right]-\left[\frac{b}{p}u\right],$ то есть ${\theta }_{a,b}(u)=0$ или $1$. Тогда $J_{a,b}(𝔏)=\prod _{u=1}^{p-1}{{\sigma }_u}^{-1}(𝔄{)}^{{\theta }_{a,b}(u)}.$Шаблон:/lemma

Шаблон:Lemma.

Для всех $a,b\in 𝐙:$ $-J_{a,b}(𝔏)=1mod{\lambda }^2.$Шаблон:/lemma

Если $p>2$, то существуют такие $a,b\in 𝐙,$ что $ab(a+b)\equiv ̸0modp$ и ${\hat{\theta }}_{a,b}\doteq \sum _{u=1}^{p-1}{\theta }_{a,b}(u)\cdot u^{-1}\equiv ̸0modp,$ где $u^{-1}$ — обратный элемент к $umodp.$Шаблон:/lemma

Шаблон:Lemma Пусть $𝔄,{𝔄}_1$ — идеалы в $𝐙[{\zeta }_q]$ такие, что $p\nmid N𝔄=N{𝔄}_1$ и пусть $\Re ,{\Re }_1$ сопряженные простые идеалы, делящие $𝔄,{𝔄}_1$ соответственно. Пускай существует такое $\gamma \in 𝐙[{\zeta }_q],$ что ${⟨\frac{\gamma }{𝔄}⟩}_p\ne 0,\ne 1$. Тогда для любого ${\alpha }_1\in 𝐙[{\zeta }_q]$ выполняется:

${⟨\frac{\gamma }{𝔄}⟩}_p^m={⟨\frac{{\alpha }_1}{{𝔄}_1}⟩}_p$

и следовательно

${⟨\frac{\gamma }{\Re }⟩}_p^m={⟨\frac{{\alpha }_1}{{\Re }_1}⟩}_p.$ Шаблон:/lemma

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

Если $n$ является составным числом, то оно имеет некий делитель $r$. Для проверки на простоту ищем это $r\ne 1,r\ne n$.

Если нам известны значения $In{d}_q(r)modp$ для каждой пары $p,q$, то по китайской теореме об остатках мы можем найти $r$. Каждая пара $p,q$ выбирается следующим образом: $p\in 𝒥(n)$, а $q$ — простое евклидово число относительно $𝒥(n)$ такое, что $p|q-1.$

В алгоритме перебираются все возможные значения $In{d}_q(r)modp$ для всех $q$, исходя из того, что известно только одно $q.$

Алгоритм

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

A. Шаг подготовки

1. Вычисляем наименьшее положительное число $f(n)$ свободное от квадратов, такое что: $\prod _{q-1|f(n)}^{qprime}q>\sqrt{n}$.

Определим множество «начальных» простых чисел, являющиеся делителями $f(n)$. Назовем $q$ евклидовым простым числом, если $q$ простое и $q-1|f(n)$

2. Проверим — делится ли $n$ на любое «начальное» или евклидово простое число. Если делитель найдется, причем не равный $n$, то объявляем $n$ составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень $t_q$ для каждого евклидового простого числа $q$.

3. Для каждого «начального» простого числа $p>2$ найдем числа $a,b$ такие, что:

$0<a,b<p$,

$a+b\equiv 0modp$,

${\hat{\theta }}_{a,b}=\sum _{u=1}^{p-1}{\theta }_{a,b}(u)\cdot u^{-1}\equiv 0modp.$

Для $p=2$ примем $a=b={\hat{\theta }}_{a,b}=1$.

4. Для каждого «начального» и евклидового простых чисел, таких что $p|q-1$ зафиксируем простой идеал:

${𝔏}_q=(q,{\zeta }_q-t_q^{(q-1)/p})$,

где $q$ принадлежит $𝖹[{\zeta }_q]$,а ${\zeta }_q=e^{2\pi i/p}$ — корень из единицы.

Вычислим сумму Якоби $J_p(q)\in 𝐐({\zeta }_q):$

если $p=2:J_p(q)=-q$,

если $p>2:J_p(q)=-J_{a,b}({𝔏}_q)=-\sum _{x=2}^{q-1}{\left(\frac{x}{{𝔏}_q}\right)}_p^{-a}{\left(\frac{1-x}{{𝔏}_q}\right)}_p^{-b}.$

B. Шаг вычислений

1. Для каждого «начального» простого числа $p$ найдем НОД в $𝐐({\zeta }_q)$ для $n$ и набора $\sigma J_p(q)$, где $q$ пробегает все значения евклидовых простых чисел, причем $p|q-1$, а $\sigma$ пробегает по всем значениям из Gal$(𝐐({\zeta }_q)/𝐐)$. Тогда либо выносим решение о том, что $n$ составное, либо строим надлежащий идеал $𝔄$ в кольце $𝐙[{\zeta }_q]$, а также находим числа $s$ и $j(\sigma ,q)$, $1\le j(\sigma ,q)\le p$ такие, что:

$(\sigma J_p(q){)}^{(n^f-1)/p^s}\equiv {{\zeta }_q}^{j(\sigma ,q)}mod𝔄$,

$p\nmid (n^f-1)/p^s$ или некоторое из ${{\zeta }_q}^{j(\sigma ,q)}\ne 1$, где $f=nmodp.$

2. Для каждого «начального» простого числа $p$ сделаем следующее: если для некоторого $j({\sigma }_0,q_0)\ne p$, тогда возьмем $\gamma ={\sigma }_0{J}_p(q_0)$. В этом ключе построим числа $m(\sigma ,q)$ для всех $\sigma ,q$, $0\le m(\sigma ,q)\le p-1$ и такие, что:

$({\gamma }^{(n^f-1)/p^s}{)}^{m(\sigma ,q)}\equiv (\sigma J_p(q){)}^{(n^f-1)/p^s}mod𝔄.$

Если же для всех $j(\sigma ,q)=p$, примем $m(\sigma ,q)=0$.

C. Шаг объединения результатов

Проделаем шаги 1-4 для всех натуральных $k,1\le k\le f(n).$

1. Для каждого $q>2$ вычислим по китайской теореме об остатках вычислим числа $I(k,q)$:

$I(k,q)=k{{\hat{\theta }}_{a,b}}^{-1}\sum _{j=1}^{p-1}j\cdot m({{\sigma }_j}^{-1},q)modp,$

при всевозможных $p$, что $p|q-1$. Так же положим, что $I(k,2)=1.$

2. Для каждого $q$ посчитаем наименьшее целое, положительное число $r(k,q)\equiv {t_q}^{I(k,q)}modq.$

3. Используя Китайскую теорему об остатках, вычислим наименьшее положительное число $r(k)$ такое, что $r(k)\equiv r(k,q)modq$ для каждого $q.$

4. Если $r(k)\ne 1,r(k)\ne n,r(k)|n$, тогда объявляем $n$ составным. Иначе переходим к следующему $k.$

5. Объявляем $n$ простым.

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

Оценка времени выполнения алгоритма вытекает из следующих теоремШаблон:Sfn:

Шаблон:Theorem Для значений $n>1$ вышеупомянутый алгоритм правильно определяет будет ли $n$ простым или составным за время $T(n)$. И справедливы следующие оценки: $f(n)\le T(n),$ для простых $n,$ $T(n)\le f^{c_1}(n),$ для всех значения $n.$ Где $c_1$ — положительная, вычисляемая константа.Шаблон:/theorem

Шаблон:Theorem Существуют такие положительные, вычисляемые константы $c_2,c_3$, что для всех $n>100:$ $(\ln (n){)}^{c_2\ln \ln \ln (n)}<f(n)<(\ln (n){)}^{c_3\ln \ln \ln (n)}$Шаблон:/theorem

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

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

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

• Шаблон:Книга
• Шаблон:Статья