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

В 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)}$.

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

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 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 с.