Тест Адлемана — Померанса — Румели (Myvm G;lybgug — Hkbyjguvg — Jrbyln)

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

Впоследствии алгоритм был улучшен Генри Коэном и Хендриком Ленстрой до 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$

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

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

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

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

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

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

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

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

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

Ind_q(x)

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

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

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

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

Сумма Якоби

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

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

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

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

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

Лемма 1.

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

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

Лемма 2.

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

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

Лемма 3.

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

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

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

Лемма 5.

Выберем $a,~b\in \mathbf {Z}$ такие, что $ab(a+b)\not \equiv 0\mod p$. Для $u\in \mathbf {Z}$ положим: $\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}({\mathfrak {L}})=\prod _{u=1}^{p-1}{\sigma _{u}}^{-1}({\mathfrak {A}})^{\theta _{a,b}(u)}~.$

Лемма 6..

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

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

Лемма 7.

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проделаем шаги 1-4 для всех натуральных $k~,1\leq k\leq 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)\mod p~,$

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

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

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

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

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

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

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

Теорема 1.

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

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

Теорема 2.

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

$(\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.

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

• Иэн Стюарт. Величайшие математические задачи. — М.: Альпина нон-фикшн, 2015. — 460 с. — ISBN 978-5-91671-318-3.
• Leonard M. Adleman, Carl Pomerance and Robert S. Rumely. [1] (англ.) = On distinguishing prime numbers from composite numbers. — 1983. — P. 7—25.