Русская Википедия:Тест Адлемана — Померанса — Румели
Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест APR) — наиболееШаблон:Sfn эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 году. Назван в честь его исследователей — Леонарда Адлемана, Карла Померанса и Шаблон:Iw. Алгоритм содержит арифметику в цикломатических полях.
Впоследствии алгоритм был улучшен Шаблон:Iw и Хендриком Ленстрой до APR-CL, время работы которого для любого числа <math>n</math> можно вычислить как <math>O((\ln n)^{c\,\ln\,\ln\,\ln n})</math>, где <math>c</math> — некоторая вычисляемая константа.
История
До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность <math>O((\ln n)^{c\,\ln\,\ln\,\ln n})</math> позволяет практическое использование алгоритма.
К примеру, для числа <math>n</math> — гуголплекс, <math>\ln \ln \ln n \approx 5{,}44282</math>
| « |
Старая шутка гласит: | » |
| — "Доказано, что <math>\log \log n</math> стремится к бесконечности, но никто никогда не видел, как он это делает." | ||
Ключевые понятия
Евклидово простое число
Пусть имеется некоторое конечное множество <math>\mathcal{J}</math> простых чисел. Если для некоторого простого числа <math>q</math> выполнены следующие условия:
- <math>q-1</math> — свободное от квадратов число
- все простые делители <math>q-1</math> принадлежат множеству <math>\mathcal{J}</math>
тогда <math>q</math> называется евклидовым простым числом относительно множества <math>\mathcal{J}</math>.
Набор «начальных» простых чисел
Для заданного числа <math>n</math> построим множество <math>\mathcal{J}=\mathcal{J}(n)</math> такое, что произведение всех евклидовых простых чисел относительно этого множества будет больше <math>\sqrt n</math>. Выберем наименьшее возможное <math>\mathcal{J}(n)</math>.
Элементы <math>p</math> из этого множества назовем набором «начальных» простых чисел.
Indq(x)
Введем некоторое число <math>Ind_q=Ind_q (x)</math>. Пусть <math>t_q</math> — его первообразный корень. Тогда должно выполняться следующее условие:
<math>x \equiv {t_q}^{Ind_q (x)} \mod q</math>,
где <math>(x,q)=1</math>.
Замечание: В качестве <math>Ind_q (x)</math> выбираем наименьшее неотрицательное число.
Сумма Якоби
Суммой Якоби называют сумму следующего вида:
<math>J_{a,b}={\sum}{\left(\frac{x}{\mathfrak{L}}\right)}_p^{-a}{\left(\frac{1-x}{\mathfrak{L}}\right)}_p^{-b}</math>,
где суммирование идет по всем наборам классов смежности для <math>x</math> в <math>\mathbf{Z}[\zeta_q]/\mathfrak{L}</math>, кроме тех, что равны <math>0,1 \mod \mathfrak{L}</math>.
Ключевые леммы
Основные леммыШаблон:Sfn, используемые при доказательстве корректности алгоритма:
Простые идеалы из <math>\mathbf{Z}[\zeta_q]</math>, лежащие над главным идеалом <math>(q)</math> это: <math> \mathfrak{L}_i = (q,h_{i}(\zeta_q))</math> для всех <math>i=1..g~.</math> Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Пусть <math>n\ge 2</math> и имеет порядок <math>f</math> в группе <math>(\mathbf{Z}/p)^{*}</math>. Возьмем <math>g=(p-1)/f</math>. Так же <math>\Phi_{p}(x)\equiv \prod^{g}_{i=1} h_{i}(x) \mod n~,</math> где <math>h_{i}(x)</math> — многочлен в <math>\mathbf{Z}[x]</math> для каждого <math>f</math>. Будем считать, что идеалы <math>\mathfrak{A}_i=(n,h_{i}(\zeta_q))~.</math> Если <math>r</math> является простым делителем <math>n</math>, тогда в <math>\mathbf{Z}[\zeta_q]</math>: <math>(r)=\prod^{g}_{i=1} (r,\mathfrak{A}_i)~,</math> и каждое <math>(r,\mathfrak{A}_i)</math>, делимое на некоторый простой идеал из <math>\mathbf{Z}[\zeta_q]</math>, лежит над <math>(r)~.</math>Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Возьмем <math>p>2</math> и элементы <math>\alpha,~\gamma \in \mathbf{Q}(\zeta_q)</math> взаимно простые с <math>\lambda</math> и относительно друг друга. <math>\left ( \frac{\alpha}{\gamma} \right )_p=~\left ( \frac{\gamma}{\alpha} \right )_p (\alpha,\gamma)_{\lambda}~.</math>
<math>(\cdot,\cdot)_\lambda</math> — символ Гильберта. Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Если <math>\alpha \equiv 1 \mod \lambda^{i},~ \gamma \equiv 1 \mod \lambda^{j},~ i+j \ge p+1 </math>, тогда <math>(\alpha,\gamma)_\lambda=1~.</math>Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Выберем <math>a,~b \in \mathbf{Z}</math> такие, что <math>ab(a+b) \not\equiv 0 \mod p</math>. Для <math>u \in \mathbf{Z}</math> положим: <math>\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>\theta_{a,b}(u) = 0</math> или <math>1</math>. Тогда <math>J_{a,b}(\mathfrak{L}) = \prod^{p-1}_{u=1}{\sigma_{u}}^{-1}(\mathfrak{A})^{\theta_{a,b}(u)}~.</math>Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Для всех <math>a,~b \in \mathbf{Z}:</math> <math>-J_{a,b}(\mathfrak{L})= 1 \mod {\lambda}^{2}~.</math>Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Если <math>p>2</math>, то существуют такие <math>a, b\in \mathbf{Z}~,</math> что <math>ab(a+b) \not\equiv 0 \mod p</math> и <math>\hat{\theta}_{a,b} \doteq \sum^{p-1}_{u=1} \theta_{a,b}(u) \cdot u^{-1}\not\equiv 0~\mod~p~,</math> где <math>u^{-1}</math> — обратный элемент к <math>u \mod p~.</math>Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Шаблон:Lemma Пусть <math>\mathfrak{A}~,~\mathfrak{A}_1</math> — идеалы в <math>\mathbf{Z}[\zeta_q]</math> такие, что <math>p \nmid N\mathfrak{A} = N\mathfrak{A}_1</math> и пусть <math>\mathfrak{R}~,~\mathfrak{R}_1</math> сопряженные простые идеалы, делящие <math>\mathfrak{A}~,~\mathfrak{A}_1</math> соответственно. Пускай существует такое <math>\gamma \in \mathbf{Z}[\zeta_q]~,</math> что <math>\left \langle \frac{\gamma}{\mathfrak{A}} \right \rangle_p \ne 0, \ne 1</math>. Тогда для любого <math>\alpha_1 \in \mathbf{Z}[\zeta_q]</math> выполняется:
<math>{\left \langle \frac{\gamma}{\mathfrak{A}} \right \rangle}_p^m={\left \langle \frac{\alpha_1}{\mathfrak{A}_1} \right \rangle_p}</math>
и следовательно
<math>{\left \langle \frac{\gamma}{\mathfrak{R}} \right \rangle}_p^m={\left \langle \frac{\alpha_1}{\mathfrak{R}_1} \right \rangle_p}~.</math> Русская Википедия:Тест Адлемана — Померанса — Румели/lemma
Идея алгоритма
Если <math>n</math> является составным числом, то оно имеет некий делитель <math>r</math>. Для проверки на простоту ищем это <math>r\ne 1~, r\ne n</math>.
Если нам известны значения <math>Ind_q (r) \mod p</math> для каждой пары <math>p, q</math>, то по китайской теореме об остатках мы можем найти <math>r</math>. Каждая пара <math>p, q</math> выбирается следующим образом: <math>p \in \mathcal{J}(n)</math>, а <math>q</math> — простое евклидово число относительно <math>\mathcal{J}(n)</math> такое, что <math>p|q-1~.</math>
В алгоритме перебираются все возможные значения <math>Ind_q (r) \mod p</math> для всех <math>q</math>, исходя из того, что известно только одно <math>q~.</math>
Алгоритм
- Ввод: целое число n > 1.
A. Шаг подготовки
1. Вычисляем наименьшее положительное число <math>f(n)</math> свободное от квадратов, такое что: <math> \prod^{q~prime}_{q-1|f(n)}q > \sqrt{n} </math>.
Определим множество «начальных» простых чисел, являющиеся делителями <math>f(n)</math>. Назовем <math>q</math> евклидовым простым числом, если <math>q</math> простое и <math>q-1|f(n)</math>
2. Проверим — делится ли <math>n</math> на любое «начальное» или евклидово простое число. Если делитель найдется, причем не равный <math>n</math>, то объявляем <math>n</math> составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень <math>t_q</math> для каждого евклидового простого числа <math>q</math>.
3. Для каждого «начального» простого числа <math>p > 2</math> найдем числа <math>a,~b</math> такие, что:
<math>0 < a, b < p</math>,
<math>a+b \equiv 0~mod~p</math>,
<math>\hat{\theta}_{a,b}=\sum^{p-1}_{u=1} \theta_{a,b}(u) \cdot u^{-1}\equiv 0~\mod~p~.</math>
Для <math>p = 2</math> примем <math>a=b=\hat{\theta}_{a,b}=1</math>.
4. Для каждого «начального» и евклидового простых чисел, таких что <math>{p|q-1}</math> зафиксируем простой идеал:
<math> \mathfrak{L}_{q} = (q, \zeta_q - t_q^{(q-1)/p})</math>,
где <math>q</math> принадлежит <math>\mathsf{Z}[\zeta_q]</math>,а <math>{\zeta_q}=e^{2\pi i/p}</math> — корень из единицы.
Вычислим сумму Якоби <math>J_p(q)\in \mathbf{Q}(\zeta_q)~:</math>
если <math>p = 2:~J_p(q)=-q</math>,
если <math>p > 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>p</math> найдем НОД в <math>\mathbf{Q}(\zeta_q)</math> для <math>n</math> и набора <math>\sigma J_p(q)</math>, где <math>q</math> пробегает все значения евклидовых простых чисел, причем <math>p|q-1</math>, а <math>\sigma</math> пробегает по всем значениям из Gal<math>(\mathbf{Q}(\zeta_q)/ \mathbf{Q})</math>. Тогда либо выносим решение о том, что <math>n</math> составное, либо строим надлежащий идеал <math> \mathfrak{A} </math> в кольце <math> \mathbf{Z}[\zeta_q] </math>, а также находим числа <math>s</math> и <math>j(\sigma,q)</math>, <math>1\le j(\sigma,q)\le p</math> такие, что:
<math>(\sigma J_p(q))^{(n^{f}-1)/{p^{s}}} \equiv {\zeta_q}^{j(\sigma,q)} ~ \mod~\mathfrak{A}</math>,
<math>p \nmid {(n^{f}-1)/{p^{s}}}</math> или некоторое из <math>{\zeta_q}^{j(\sigma,q)} \ne 1</math>, где <math>f= n~\mod~p~.</math>
2. Для каждого «начального» простого числа <math>p</math> сделаем следующее: если для некоторого <math>j(\sigma_0,q_0)\ne p</math>, тогда возьмем <math>\gamma=\sigma_0 J_p(q_0)</math>. В этом ключе построим числа <math>m(\sigma,q)</math> для всех <math>\sigma,q</math>, <math>0\le m(\sigma,q)\le p-1</math> и такие, что:
<math>(\gamma^{(n^{f}-1)/{p^{s}}})^{m(\sigma,q)}\equiv (\sigma J_p(q))^{(n^{f}-1)/{p^{s}}} \mod~\mathfrak{A} .</math>
Если же для всех <math>j(\sigma,q)~=~p</math>, примем <math>m(\sigma,q)~=~0</math>.
C. Шаг объединения результатов
Проделаем шаги 1-4 для всех натуральных <math>k~,1\le k \le f(n).</math>
1. Для каждого <math>q>2</math> вычислим по китайской теореме об остатках вычислим числа <math>I(k,q)</math>:
<math>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>p</math>, что <math>p|q-1</math>. Так же положим, что <math>I(k,2)=1~.</math>
2. Для каждого <math>q</math> посчитаем наименьшее целое, положительное число <math>r(k,q)\equiv {t_q}^{I(k,q)}\mod q.</math>
3. Используя Китайскую теорему об остатках, вычислим наименьшее положительное число <math>r(k)</math> такое, что <math>r(k)\equiv r(k,q) \mod q</math> для каждого <math>q~.</math>
4. Если <math>r(k)\ne 1~,~r(k)\ne n~, r(k)|n</math>, тогда объявляем <math>n</math> составным. Иначе переходим к следующему <math>k~.</math>
5. Объявляем <math>n</math> простым.
Оценка сложности
Оценка времени выполнения алгоритма вытекает из следующих теоремШаблон:Sfn:
Шаблон:Theorem Для значений <math>n>1</math> вышеупомянутый алгоритм правильно определяет будет ли <math>n</math> простым или составным за время <math>T(n)</math>. И справедливы следующие оценки: <math>f(n)\le T(n)~,</math> для простых <math>n~,</math> <math>T(n)\le f^{c_1}(n)~,</math> для всех значения <math>n~.</math> Где <math>c_1</math> — положительная, вычисляемая константа.Русская Википедия:Тест Адлемана — Померанса — Румели/theorem
Шаблон:Theorem Существуют такие положительные, вычисляемые константы <math>c_2,~c_3</math>, что для всех <math>n>100~:</math> <math>(\ln (n))^{c_2 \ln \ln \ln (n)} < f(n) < (\ln (n))^{c_3 \ln \ln \ln (n)}</math>Русская Википедия:Тест Адлемана — Померанса — Румели/theorem
Программная реализация
- В Шаблон:Iw приведена реализация алгоритма под именем APRT-CLE (APR Test CL extended)
- factoring applet использует алгоритм APR-CL с определёнными условиями
- Pari/GP условное использование APR-CL в реализации isprime().
- mpz_aprcl реализация с открытым исходным кодом. Использует C + GMP.
Примечания
Список литературы
