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

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

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

История

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

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

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

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

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

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

1. ${\displaystyle q-1}$ — свободное от квадратов число
2. все простые делители ${\displaystyle q-1}$ принадлежат множеству ${\displaystyle {\mathcal {J}}}$

тогда ${\displaystyle q}$ называется евклидовым простым числом относительно множества ${\displaystyle {\mathcal {J}}}$.

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

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

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

Ind_q(x)

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

${\displaystyle x\equiv {t_{q}}^{Ind_{q}(x)}\mod q}$,

где ${\displaystyle (x,q)=1}$.

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

Сумма Якоби

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

${\displaystyle J_{a,b}={\sum }{\left({\frac {x}{\mathfrak {L}}}\right)}_{p}^{-a}{\left({\frac {1-x}{\mathfrak {L}}}\right)}_{p}^{-b}}$,

где суммирование идет по всем наборам классов смежности для ${\displaystyle x}$ в ${\displaystyle \mathbf {Z} [\zeta _{q}]/{\mathfrak {L}}}$, кроме тех, что равны ${\displaystyle 0,1\mod {\mathfrak {L}}}$.

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

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

Лемма 1.

Простые идеалы из ${\displaystyle \mathbf {Z} [\zeta _{q}]}$, лежащие над главным идеалом ${\displaystyle (q)}$ это:

${\displaystyle {\mathfrak {L}}_{i}=(q,h_{i}(\zeta _{q}))}$ для всех ${\displaystyle i=1..g~.}$

Лемма 2.

Пусть ${\displaystyle n\geq 2}$ и имеет порядок ${\displaystyle f}$ в группе ${\displaystyle (\mathbf {Z} /p)^{*}}$. Возьмем ${\displaystyle g=(p-1)/f}$. Так же ${\displaystyle \Phi _{p}(x)\equiv \prod _{i=1}^{g}h_{i}(x)\mod n~,}$ где ${\displaystyle h_{i}(x)}$ — многочлен в ${\displaystyle \mathbf {Z} [x]}$ для каждого ${\displaystyle f}$. Будем считать, что идеалы ${\displaystyle {\mathfrak {A}}_{i}=(n,h_{i}(\zeta _{q}))~.}$ Если ${\displaystyle r}$ является простым делителем ${\displaystyle n}$, тогда в ${\displaystyle \mathbf {Z} [\zeta _{q}]}$: ${\displaystyle (r)=\prod _{i=1}^{g}(r,{\mathfrak {A}}_{i})~,}$

и каждое ${\displaystyle (r,{\mathfrak {A}}_{i})}$, делимое на некоторый простой идеал из ${\displaystyle \mathbf {Z} [\zeta _{q}]}$, лежит над ${\displaystyle (r)~.}$

Лемма 3.

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

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

Лемма 4. Если ${\displaystyle \alpha \equiv 1\mod \lambda ^{i},~\gamma \equiv 1\mod \lambda ^{j},~i+j\geq p+1}$, тогда ${\displaystyle (\alpha ,\gamma )_{\lambda }=1~.}$

Лемма 5.

Выберем ${\displaystyle a,~b\in \mathbf {Z} }$ такие, что ${\displaystyle ab(a+b)\not \equiv 0\mod p}$. Для ${\displaystyle u\in \mathbf {Z} }$ положим: ${\displaystyle \theta _{a,b}(u)=\left[{\frac {a+b}{p}}{u}\right]-\left[{\frac {a}{p}}{u}\right]-\left[{\frac {b}{p}}{u}\right],}$ то есть ${\displaystyle \theta _{a,b}(u)=0}$ или ${\displaystyle 1}$.

Тогда ${\displaystyle J_{a,b}({\mathfrak {L}})=\prod _{u=1}^{p-1}{\sigma _{u}}^{-1}({\mathfrak {A}})^{\theta _{a,b}(u)}~.}$

Лемма 6.^[3].

Для всех ${\displaystyle a,~b\in \mathbf {Z}$ :}

${\displaystyle -J_{a,b}({\mathfrak {L}})=1\mod {\lambda }^{2}~.}$

Лемма 7.

Если ${\displaystyle p>2}$, то существуют такие ${\displaystyle a,b\in \mathbf {Z} ~,}$ что ${\displaystyle ab(a+b)\not \equiv 0\mod p}$ и

${\displaystyle {\hat {\theta }}_{a,b}\doteq \sum _{u=1}^{p-1}\theta _{a,b}(u)\cdot u^{-1}\not \equiv 0~\mod ~p~,}$ где ${\displaystyle u^{-1}}$ — обратный элемент к ${\displaystyle u\mod p~.}$

Лемма (Извлечения).

Пусть ${\displaystyle {\mathfrak {A}}~,~{\mathfrak {A}}_{1}}$ — идеалы в ${\displaystyle \mathbf {Z} [\zeta _{q}]}$ такие, что ${\displaystyle p\nmid N{\mathfrak {A}}=N{\mathfrak {A}}_{1}}$ и пусть ${\displaystyle {\mathfrak {R}}~,~{\mathfrak {R}}_{1}}$ сопряженные простые идеалы, делящие ${\displaystyle {\mathfrak {A}}~,~{\mathfrak {A}}_{1}}$ соответственно. Пускай существует такое ${\displaystyle \gamma \in \mathbf {Z} [\zeta _{q}]~,}$ что ${\displaystyle \left\langle {\frac {\gamma }{\mathfrak {A}}}\right\rangle _{p}\neq 0,\neq 1}$. Тогда для любого ${\displaystyle \alpha _{1}\in \mathbf {Z} [\zeta _{q}]}$ выполняется:

${\displaystyle {\left\langle {\frac {\gamma }{\mathfrak {A}}}\right\rangle }_{p}^{m}={\left\langle {\frac {\alpha _{1}}{{\mathfrak {A}}_{1}}}\right\rangle _{p}}}$

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

${\displaystyle {\left\langle {\frac {\gamma }{\mathfrak {R}}}\right\rangle }_{p}^{m}={\left\langle {\frac {\alpha _{1}}{{\mathfrak {R}}_{1}}}\right\rangle _{p}}~.}$

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

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

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

В алгоритме перебираются все возможные значения ${\displaystyle Ind_{q}(r)\mod p}$ для всех ${\displaystyle q}$, исходя из того, что известно только одно ${\displaystyle q~.}$

Алгоритм

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

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

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

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

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

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

${\displaystyle 0<a,b<p}$,

${\displaystyle a+b\equiv 0~mod~p}$,

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

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

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

${\displaystyle {\mathfrak {L}}_{q}=(q,\zeta _{q}-t_{q}^{(q-1)/p})}$,

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

Вычислим сумму Якоби ${\displaystyle J_{p}(q)\in \mathbf {Q} (\zeta _{q})~:}$

если ${\displaystyle p=2:~J_{p}(q)=-q}$,

если ${\displaystyle p>2:~J_{p}(q)=-J_{a,b}({\mathfrak {L}}_{q})=-\sum _{x=2}^{q-1}{\left({\frac {x}{{\mathfrak {L}}_{q}}}\right)}_{p}^{-a}{\left({\frac {1-x}{{\mathfrak {L}}_{q}}}\right)}_{p}^{-b}.}$

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

1. Для каждого «начального» простого числа ${\displaystyle p}$ найдем НОД в ${\displaystyle \mathbf {Q} (\zeta _{q})}$ для ${\displaystyle n}$ и набора ${\displaystyle \sigma J_{p}(q)}$, где ${\displaystyle q}$ пробегает все значения евклидовых простых чисел, причем ${\displaystyle p|q-1}$, а ${\displaystyle \sigma }$ пробегает по всем значениям из Gal${\displaystyle (\mathbf {Q} (\zeta _{q})/\mathbf {Q} )}$. Тогда либо выносим решение о том, что ${\displaystyle n}$ составное, либо строим надлежащий идеал ${\displaystyle {\mathfrak {A}}}$ в кольце ${\displaystyle \mathbf {Z} [\zeta _{q}]}$, а также находим числа ${\displaystyle s}$ и ${\displaystyle j(\sigma ,q)}$, ${\displaystyle 1\leq j(\sigma ,q)\leq p}$ такие, что:

${\displaystyle (\sigma J_{p}(q))^{(n^{f}-1)/{p^{s}}}\equiv {\zeta _{q}}^{j(\sigma ,q)}~\mod ~{\mathfrak {A}}}$,

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

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

${\displaystyle (\gamma ^{(n^{f}-1)/{p^{s}}})^{m(\sigma ,q)}\equiv (\sigma J_{p}(q))^{(n^{f}-1)/{p^{s}}}\mod ~{\mathfrak {A}}.}$

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

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

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

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

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

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

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

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

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

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

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

Оценка времени выполнения алгоритма вытекает из следующих теорем^[2]:

Теорема 1.

Для значений ${\displaystyle n>1}$ вышеупомянутый алгоритм правильно определяет будет ли ${\displaystyle n}$ простым или составным за время ${\displaystyle T(n)}$. И справедливы следующие оценки: ${\displaystyle f(n)\leq T(n)~,}$ для простых ${\displaystyle n~,}$

${\displaystyle T(n)\leq f^{c_{1}}(n)~,}$ для всех значения ${\displaystyle n~.}$ Где ${\displaystyle c_{1}}$ — положительная, вычисляемая константа.

Теорема 2.

Существуют такие положительные, вычисляемые константы ${\displaystyle c_{2},~c_{3}}$, что для всех ${\displaystyle n>100~:}$

${\displaystyle (\ln(n))^{c_{2}\ln \ln \ln(n)}<f(n)<(\ln(n))^{c_{3}\ln \ln \ln(n)}}$

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

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