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

Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест 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$ выполнены следующие условия:

$q-1$ — свободное от квадратов число
все простые делители $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)}

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

В приведена реализация алгоритма под именем APRT-CLE (APR Test CL extended)
использует алгоритм APR-CL с определёнными условиями
условное использование APR-CL в реализации isprime().
реализация с открытым исходным кодом . Использует C + GMP.

Примечания

.
↑ .
K. Iwasawa. A note on jacobi sum (англ.) // Symposia Math. — 1975. — С. 447—459 .

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

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