Алгоритм Диксона

В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению ${\displaystyle x^{2}-y^{2}=n}$ , искать пары чисел, удовлетворяющих более общему уравнению ${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}$ . Крайчик заметил несколько полезных для решения фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод факторизации, использующий идеи Крайтчика, и рассчитал его вычислительную сложность.^[2]

1. Составить факторную базу ${\displaystyle \mathrm {B} =\left\{{p_{1},p_{2},\dots ,p_{h}}\right\}}$ , состоящую из всех простых чисел ${\displaystyle p<=M=L\left({n}\right)^{\frac {1}{2}}}$ , где ${\displaystyle L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n}}}}\right)}}$ .
2. Выбрать случайное ${\displaystyle b,{\sqrt {n}}<b<n}$
3. Вычислить ${\displaystyle a=b^{2}{\bmod {n}}}$ .
4. Проверить число ${\displaystyle a}$ на гладкость пробными делениями. Если ${\displaystyle a}$ является ${\displaystyle \mathrm {B} }$ -гладким числом, то есть ${\displaystyle a=\prod _{p\in \mathrm {B} }p^{\alpha _{p}\left({b}\right)}}$ , следует запомнить вектора ${\displaystyle {\vec {\alpha }}\left({b}\right)}$ и ${\displaystyle {\vec {\varepsilon }}\left({b}\right)}$ :

   ${\displaystyle {\vec {\alpha }}\left({b}\right)=\left({\alpha _{p_{1}}\left({b}\right),\dots ,\alpha _{p_{h}}\left({b}\right)}\right)}$

   ${\displaystyle {\vec {\varepsilon }}\left({b}\right)=\left({\alpha _{p_{1}}\left({b}\right){\bmod {2}},\dots ,\alpha _{p_{h}}\left({b}\right){\bmod {2}}}\right)}$ .

5. Повторять процедуру генерации чисел ${\displaystyle b}$ до тех пор, пока не будет найдено ${\displaystyle h+1}$ ${\displaystyle \mathrm {B} }$ -гладких чисел ${\displaystyle b_{1},...,b_{h+1}}$ .
6. Методом Гаусса найти линейную зависимость среди векторов ${\displaystyle {\vec {\varepsilon }}\left({b_{1}}\right),\dots ,{\vec {\varepsilon }}\left({b_{h+1}}\right)}$ :

   ${\displaystyle {\vec {\varepsilon }}\left({b_{i_{1}}}\right)\oplus \dots \oplus {\vec {\varepsilon }}\left({b_{i_{t}}}\right)={\vec {0}},1\leqslant t\leqslant m}$

   и положить:

   ${\displaystyle x=b_{i_{1}}\dots b_{i_{t}}{\bmod {n}}}$

   ${\displaystyle y=\prod _{p\in \mathrm {B} }p^{\left({\alpha _{p}\left({b_{i_{1}}}\right)+\dots +\alpha _{p}\left({b_{i_{t}}}\right)}\right) \over {2}}{\bmod {n}}}$ .

7. Проверить ${\displaystyle x\equiv \pm y{\pmod {n}}}$ . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

   ${\displaystyle n=u\cdot v,u=gcd\left({x+y,n}\right),v=gcd\left({x-y,n}\right).}$

Факторизуем число ${\displaystyle n=89755}$ .

${\displaystyle L(89755)=194,174...}$

${\displaystyle M=13,934...}$

${\displaystyle \mathrm {B} =\left\{2,3,5,7,11,13\right\}}$

Все найденные числа ${\displaystyle b}$ с соответствующими векторами ${\displaystyle {\vec {\alpha }}(b)}$ записываем в таблицу.

${\displaystyle b}$	${\displaystyle a}$	${\displaystyle \alpha _{2}\left({b}\right)}$	${\displaystyle \alpha _{3}\left({b}\right)}$	${\displaystyle \alpha _{5}\left({b}\right)}$	${\displaystyle \alpha _{7}\left({b}\right)}$	${\displaystyle \alpha _{11}\left({b}\right)}$	${\displaystyle \alpha _{13}\left({b}\right)}$
337	23814	1	5	0	2	0	0
430	5390	1	0	1	2	1	0
519	96	5	1	0	0	0	0
600	980	2	0	1	2	0	0
670	125	0	0	3	0	0	0
817	39204	2	4	0	0	2	0
860	21560	3	0	1	2	1	0

Решая линейную систему уравнений, получаем, что ${\displaystyle {\vec {\varepsilon }}\left(337\right)\oplus {\vec {\varepsilon }}\left(519\right)={\vec {0}}}$ . Тогда

${\displaystyle x=337\cdot 519{\bmod {89755}}=85148}$

${\displaystyle y=2^{3}\cdot 3^{3}\cdot 7^{1}{\bmod {89755}}=1512}$

${\displaystyle 85148\not \equiv \pm 1512{\pmod {89755}}}$

Следовательно,

${\displaystyle u=gcd(86660,89755)=3095}$

${\displaystyle v=gcd(83636,89755)=29}$ .

Получилось разложение ${\displaystyle 89755=3095\cdot 29}$

Обозначим через ${\displaystyle \Psi (n,M)}$ количество целых чисел ${\displaystyle a}$ таких, что ${\displaystyle 1<a\leqslant n}$ и ${\displaystyle a}$ является ${\displaystyle \mathrm {B} }$ -гладким числом, где ${\displaystyle \mathrm {B} =\{p:p<M\}}$ . Из теоремы де Брёйна — Эрдёша ${\displaystyle \Psi (n,M)=n\cdot u^{-u}}$ , где ${\displaystyle u={\frac {\ln {n}}{\ln {M}}}}$ . Значит, каждое ${\displaystyle \mathrm {B} }$ -гладкое число будет в среднем попадаться с ${\displaystyle u^{u}}$ попыток. Для проверки, является ли число ${\displaystyle \mathrm {B} }$ -гладким, необходимо выполнить ${\displaystyle h}$ делений. По алгоритму необходимо найти ${\displaystyle h+1}$ ${\displaystyle \mathrm {B} }$ -гладкое число. Значит, вычислительная сложность поиска чисел

${\displaystyle T_{1}=O\left({u^{u}\cdot h^{2}}\right)}$ .

Вычислительная сложность метода Гаусса из ${\displaystyle h}$ уравнений

${\displaystyle T_{2}=O\left({h^{3}}\right)}$ .

Следовательно, суммарная сложность алгоритма Диксона

${\displaystyle T=T_{1}+T_{2}=O\left({u^{u}\cdot h^{2}+h^{3}}\right)}$ .

Учитывая, что количество простых чисел меньше ${\displaystyle M}$ оценивается формулой ${\displaystyle h={\frac {M}{\ln {M}}}}$ , и что ${\displaystyle u={\frac {\ln {n}}{\ln {M}}}}$ , после упрощения получаем

${\displaystyle T=O\left(exp({\frac {\ln {n}\cdot \ln {\ln {n}}}{\ln {M}}}+2\ln {M})\right)}$ .

${\displaystyle M}$ выбирается таким образом, чтобы ${\displaystyle T}$ было минимально. Тогда подставляя ${\displaystyle L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n}}}}\right)}}$ , получаем

${\displaystyle M=\left({\frac {L\left({n}\right)}{2}}\right)^{\frac {1}{2}}}$

${\displaystyle T=O\left({L\left({n}\right)}^{2{\sqrt {2}}}\right)}$ .

Оценка, сделанная Померанцем на основании более строгой теоремы, чем теорема де Брёйна — Эрдеша^[6], дает ${\displaystyle T=O\left({L\left({n}\right)}^{2}\right)}$ , в то время как изначальная оценка сложности, сделанная самим Диксоном, дает ${\displaystyle T=O\left({L\left({n}\right)}^{3{\sqrt {2}}}\right)}$ .

Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.

Стратегия LP

Стратегия LP (Large Prime variation) использует большие простые числа для ускорения процедуры генерации чисел ${\displaystyle b}$ .

Алгоритм

Пусть найденное в пункте 4 число ${\displaystyle a}$ не является ${\displaystyle \mathrm {B} }$ -гладким. Тогда его можно представить ${\displaystyle a=s\cdot \prod _{p\in \mathrm {B} }p^{\alpha _{p}\left({b}\right)}}$ , где ${\displaystyle s}$ не делится на числа из факторной базы.Очевидно, что ${\displaystyle s>M}$ . Если дополнительно выполняется ${\displaystyle s<M^{2}}$ , то s — простое и мы включаем его в факторную базу. Это позволяет найти дополнительные ${\displaystyle \mathrm {B} }$ -гладкие числа, но увеличивает количество необходимых гладких чисел на 1.Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого ${\displaystyle s}$ входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть ${\displaystyle s}$ из факторной базы. Если же, например, таких чисел два ${\displaystyle b_{1}}$ и ${\displaystyle b_{2}}$ , то их нужно вычеркнуть и добавить число ${\displaystyle b=b_{1}\cdot b_{2}}$ . Показатель ${\displaystyle s}$ войдет в разложение ${\displaystyle b^{2}{\bmod {n}}}$ в четной степени и будет отсутствовать в системе линейных уравнений.

Вариация стратегии

Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.

Вычислительная сложность

Теоретическая оценка сложности алгоритма с применением LP стратегии, сделанная Померанцем, не отличается от оценки исходного варианта алгоритма Диксона:

${\displaystyle T_{LP}=O\left({L\left({n}\right)}^{2}\right)}$ .

Стратегия EAS

Стратегия EAS (раннего обрыва) исключает некоторые ${\displaystyle b}$ из рассмотрения, не доводя проверку ${\displaystyle a}$ на гладкость до конца.

Алгоритм

Выбираются фиксированные ${\displaystyle 0<k,l,m<1}$ . В алгоритме Диксона ${\displaystyle a}$ факторизуется пробными делениями на ${\displaystyle p<M=L\left({n}\right)^{\frac {1}{2}}}$ . В стратегии EAS выбирается ${\displaystyle M=L\left({n}\right)^{k}}$ и число сначала факторизуется пробными делениями на ${\displaystyle p<M^{l}=L\left({n}\right)^{kl}}$ , и если после разложения неразложенная часть остается больше, чем ${\displaystyle n^{1-m}}$ , то данное ${\displaystyle b}$ отбрасывается.

Вариация стратегии

Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности ${\displaystyle l_{j}}$ и убывающей последовательности ${\displaystyle m_{j}}$ .

Вычислительная сложность

Алгоритм Диксона с применением стратегии EAS при ${\displaystyle k={\sqrt {\frac {2}{7}}},l={\frac {1}{2}},m={\frac {1}{7}}}$ оценивается

${\displaystyle T_{EAS}=O\left({L\left({n}\right)}^{\sqrt {\frac {7}{2}}}\right)}$ .

Стратегия PS

Стратегия PS использует алгоритм Полларда-Штрассена, который для ${\displaystyle z,t\in \mathbb {N} }$ и ${\displaystyle y=z^{2}}$ находит минимальный простой делитель числа НОД${\displaystyle (t,y!)}$ за ${\displaystyle O\left(z\cdot \ln ^{2}{z}\cdot \ln ^{2}{t}\right)}$ .^[8]

Алгоритм

Выбирается фиксированное ${\displaystyle 0<k<1}$ . В алгоритме Диксона ${\displaystyle a}$ факторизуется пробными делениями на ${\displaystyle p<M=L\left({n}\right)^{\frac {1}{2}}}$ . В стратегии PS выбирается ${\displaystyle M=L\left({n}\right)^{k}}$ . Полагаем ${\displaystyle z=[L\left({n}\right)^{\frac {k}{2}}]+1,y=z^{2}\geqslant L\left({n}\right)^{k},t=a}$ . Применяем алгоритм Полларда-Штрассена, выбирая за ${\displaystyle t}$ неразложенную часть, получим разложение ${\displaystyle a}$ .

Вычислительная сложность

Сложность алгоритма Диксона со стратегией PS минимальна при ${\displaystyle k={\frac {1}{\sqrt {3}}}}$ и равна

${\displaystyle T_{PS}=O\left({L\left({n}\right)}^{\sqrt {3}}\right)}$ .

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 78-83. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2001. — С. 74-80. — 104 с. — ISBN 5-94057-060-7. Архивная копия от 31 мая 2013 на Wayback Machine
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань: Казан. ун., 2011. — С. 115-117. — 190 с.