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

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

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

История Шаблон:Sfn

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

Описание алгоритма Шаблон:Sfn

• Составить факторную базу $P=\left\{p_1,p_2,\dots ,p_h\right\}$, состоящую из всех простых чисел $p<=\mathrm{B}=L{\left(n\right)}^{\frac{1}{2}}$, где $L\left(n\right)=\exp \left(\sqrt{\ln n\cdot \ln \ln n}\right)$.
• Выбрать случайное $b,\sqrt{n}<b<n$
• Вычислить $a=b^{2}modn$.
• Проверить число $a$ на гладкость пробными делениями. Если $a$ является $\mathrm{B}$-гладким числом, то есть $a=\prod _{p\in \mathrm{B}}{p}^{{\alpha }_p\left(b\right)}$, следует запомнить вектора $\overrightarrow{\alpha }\left(b\right)$ и $\overrightarrow{\epsilon }\left(b\right)$:

$\overrightarrow{\alpha }\left(b\right)=\left({\alpha }_{p_1}\left(b\right),\dots ,{\alpha }_{p_h}\left(b\right)\right)$

$\overrightarrow{\epsilon }\left(b\right)=\left({\alpha }_{p_1}\left(b\right)mod2,\dots ,{\alpha }_{p_h}\left(b\right)mod2\right)$.

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

$\overrightarrow{\epsilon }\left(b_{i_1}\right)\oplus \dots \oplus \overrightarrow{\epsilon }\left(b_{i_t}\right)=\overrightarrow{0},1⩽t⩽m$

и положить:

$x=b_{i_1}\dots b_{i_t}modn$

$y=\prod _{p\in \mathrm{B}}{p}^{\frac{\left({\alpha }_p\left(b_{i_1}\right)+\dots +{\alpha }_p\left(b_{i_t}\right)\right)}{2}}modn$.

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

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

Пример

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

$L(89755)=194,174\dots$

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

$P=\{2,3,5,7,11,13\}$

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

$b$	$a$	${\alpha }_2\left(b\right)$	${\alpha }_3\left(b\right)$	${\alpha }_5\left(b\right)$	${\alpha }_7\left(b\right)$	${\alpha }_{11}\left(b\right)$	${\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

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

$x=337\cdot 519mod89755=85148$

$y=2^3\cdot 3^3\cdot 7^{1}mod89755=1512$

$85148\equiv ̸\pm 1512(\mathrm{mod}89755)$

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

$u=gcd(86660,89755)=3095$

$v=gcd(83636,89755)=29$.

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

Вычислительная сложность Шаблон:Sfn

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

$T_1=O\left(u^u\cdot h^2\right)$.

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

$T_2=O\left(h^3\right)$.

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

$T=T_1+T_2=O\left(u^u\cdot h^2+h^3\right)$.

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

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

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

$\mathrm{B}={\left(\frac{L\left(n\right)}{2}\right)}^{\frac{1}{2}}$

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

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

Дополнительные стратегии Шаблон:Sfn

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

Стратегия LP

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

Алгоритм

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

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

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

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

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

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

Стратегия EAS

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

Алгоритм

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

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

Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности $l_j$ и убывающей последовательности $m_j$.

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

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

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

Стратегия PS

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

Алгоритм

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

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

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

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

Литература

• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга