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

Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел ${\displaystyle x}$ и ${\displaystyle y}$ таких, что ${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}$ и ${\displaystyle x\not \equiv \pm y{\pmod {n}}.}$

Метод Диксона является обобщением метода Ферма.

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

1. Составить факторную базу ${\displaystyle P=\left\{{p_{1},p_{2},\dots ,p_{h}}\right\}}$, состоящую из всех простых чисел ${\displaystyle p<=\mathrm {B} =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\dots }$

${\displaystyle \mathrm {B} =13{,}934\dots }$

${\displaystyle P=\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,\mathrm {B} )}$ количество целых чисел ${\displaystyle a}$ таких, что ${\displaystyle 1<a\leqslant n}$ и ${\displaystyle a}$ является ${\displaystyle \mathrm {B} }$-гладким числом. Из теоремы де Брёйна — Эрдёша ${\displaystyle \Psi (n,\mathrm {B} )=n\cdot u^{-u}}$, где ${\displaystyle u={\frac {\ln {n}}{\ln {\mathrm {B} }}}}$. Значит, каждое ${\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 {\mathrm {B} }{\ln {\mathrm {B} }}}}$, и что ${\displaystyle u={\frac {\ln {n}}{\ln {\mathrm {B} }}}}$, после упрощения получаем

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

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

${\displaystyle \mathrm {B} =\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 (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>B}$. Если дополнительно выполняется ${\displaystyle s<\mathrm {B} ^{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 (раннего обрыва) исключает некоторые ${\displaystyle b}$ из рассмотрения, не доводя проверку ${\displaystyle a}$ на гладкость до конца.

Выбираются фиксированные ${\displaystyle 0<k,l,m<1}$. В алгоритме Диксона ${\displaystyle a}$ факторизуется пробными делениями на ${\displaystyle p<\mathrm {B} =L\left({n}\right)^{\frac {1}{2}}}$. В стратегии EAS выбирается ${\displaystyle \mathrm {B} =L\left({n}\right)^{k}}$ и число сначала факторизуется пробными делениями на ${\displaystyle p<\mathrm {B} ^{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 использует алгоритм Полларда-Штрассена, который для ${\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<\mathrm {B} =L\left({n}\right)^{\frac {1}{2}}}$. В стратегии PS выбирается ${\displaystyle \mathrm {B} =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 с.