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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

Ind_q(x)

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

[math]\displaystyle{ x \equiv {t_q}^{Ind_q (x)} \mod q }[/math],

где [math]\displaystyle{ (x,q)=1 }[/math].

Замечание: В качестве [math]\displaystyle{ Ind_q (x) }[/math] выбираем наименьшее неотрицательное число.

Сумма Якоби

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

[math]\displaystyle{ J_{a,b}={\sum}{\left(\frac{x}{\mathfrak{L}}\right)}_p^{-a}{\left(\frac{1-x}{\mathfrak{L}}\right)}_p^{-b} }[/math],

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

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

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

Лемма 1.

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

[math]\displaystyle{ \mathfrak{L}_i = (q,h_{i}(\zeta_q)) }[/math] для всех [math]\displaystyle{ i=1..g~. }[/math]

Лемма 2.

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

и каждое [math]\displaystyle{ (r,\mathfrak{A}_i) }[/math], делимое на некоторый простой идеал из [math]\displaystyle{ \mathbf{Z}[\zeta_q] }[/math], лежит над [math]\displaystyle{ (r)~. }[/math]

Лемма 3.

Возьмем [math]\displaystyle{ p\gt 2 }[/math] и элементы [math]\displaystyle{ \alpha,~\gamma \in \mathbf{Q}(\zeta_q) }[/math] взаимно простые с [math]\displaystyle{ \lambda }[/math] и относительно друг друга. [math]\displaystyle{ \left ( \frac{\alpha}{\gamma} \right )_p=~\left ( \frac{\gamma}{\alpha} \right )_p (\alpha,\gamma)_{\lambda}~. }[/math]

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

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

Лемма 5.

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

Тогда [math]\displaystyle{ J_{a,b}(\mathfrak{L}) = \prod^{p-1}_{u=1}{\sigma_{u}}^{-1}(\mathfrak{A})^{\theta_{a,b}(u)}~. }[/math]

Лемма 6..

Для всех [math]\displaystyle{ a,~b \in \mathbf{Z}: }[/math]

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

Лемма 7.

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

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

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

Пусть [math]\displaystyle{ \mathfrak{A}~,~\mathfrak{A}_1 }[/math] — идеалы в [math]\displaystyle{ \mathbf{Z}[\zeta_q] }[/math] такие, что [math]\displaystyle{ p \nmid N\mathfrak{A} = N\mathfrak{A}_1 }[/math] и пусть [math]\displaystyle{ \mathfrak{R}~,~\mathfrak{R}_1 }[/math] сопряженные простые идеалы, делящие [math]\displaystyle{ \mathfrak{A}~,~\mathfrak{A}_1 }[/math] соответственно. Пускай существует такое [math]\displaystyle{ \gamma \in \mathbf{Z}[\zeta_q]~, }[/math] что [math]\displaystyle{ \left \langle \frac{\gamma}{\mathfrak{A}} \right \rangle_p \ne 0, \ne 1 }[/math]. Тогда для любого [math]\displaystyle{ \alpha_1 \in \mathbf{Z}[\zeta_q] }[/math] выполняется:

[math]\displaystyle{ {\left \langle \frac{\gamma}{\mathfrak{A}} \right \rangle}_p^m={\left \langle \frac{\alpha_1}{\mathfrak{A}_1} \right \rangle_p} }[/math]

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

[math]\displaystyle{ {\left \langle \frac{\gamma}{\mathfrak{R}} \right \rangle}_p^m={\left \langle \frac{\alpha_1}{\mathfrak{R}_1} \right \rangle_p}~. }[/math]

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

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

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

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

Алгоритм

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

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

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

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

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

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

[math]\displaystyle{ 0 \lt a, b \lt p }[/math],

[math]\displaystyle{ a+b \equiv 0~mod~p }[/math],

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

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

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

[math]\displaystyle{ \mathfrak{L}_{q} = (q, \zeta_q - t_q^{(q-1)/p}) }[/math],

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

Вычислим сумму Якоби [math]\displaystyle{ J_p(q)\in \mathbf{Q}(\zeta_q)~: }[/math]

если [math]\displaystyle{ p = 2:~J_p(q)=-q }[/math],

если [math]\displaystyle{ p \gt 2:~J_p(q)=-J_{a,b}(\mathfrak{L}_{q})=-\sum^{q-1}_{x=2} {\left(\frac{x}{\mathfrak{L}_{q}}\right)}_p^{-a}{\left(\frac{1-x}{\mathfrak{L}_{q}}\right)}_p^{-b}. }[/math]

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

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

[math]\displaystyle{ (\sigma J_p(q))^{(n^{f}-1)/{p^{s}}} \equiv {\zeta_q}^{j(\sigma,q)} ~ \mod~\mathfrak{A} }[/math],

[math]\displaystyle{ p \nmid {(n^{f}-1)/{p^{s}}} }[/math] или некоторое из [math]\displaystyle{ {\zeta_q}^{j(\sigma,q)} \ne 1 }[/math], где [math]\displaystyle{ f= n~\mod~p~. }[/math]

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

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

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

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

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

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

[math]\displaystyle{ I(k,q)=k{\hat{\theta}_{a,b}}^{-1}\sum^{p-1}_{j=1} j\cdot m({\sigma_j}^{-1},q)\mod p~, }[/math]

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

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

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

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

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

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

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

Теорема 1.

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

[math]\displaystyle{ T(n)\le f^{c_1}(n)~, }[/math] для всех значения [math]\displaystyle{ n~. }[/math] Где [math]\displaystyle{ c_1 }[/math] — положительная, вычисляемая константа.

Теорема 2.

Существуют такие положительные, вычисляемые константы [math]\displaystyle{ c_2,~c_3 }[/math], что для всех [math]\displaystyle{ n\gt 100~: }[/math]

[math]\displaystyle{ (\ln (n))^{c_2 \ln \ln \ln (n)} \lt f(n) \lt (\ln (n))^{c_3 \ln \ln \ln (n)} }[/math]

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

• В 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.