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

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

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

История ^[1]

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

Описание алгоритма ^[3]

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

   $\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\right)}\right)$

   $\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. Повторять процедуру генерации чисел $b$ до тех пор, пока не будет найдено $h+1$ $\Beta$-гладких чисел $b_1,...,b_{h+1}$.
6. Методом Гаусса найти линейную зависимость среди векторов $\vec{\varepsilon}\left({b_1}\right), \dots, \vec{\varepsilon}\left({b_{h+1}}\right)$:

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

   и положить:

   $x=b_{i_1} \dots b_{i_t}\bmod{n}$

   $y=\prod_{p\isin\Beta}p^{\left({ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }\right) \over{2}}\bmod{n}$.

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

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

Доказательство корректности ^[4]  

1. Чтобы формула для $y$ была корректной, сумма $\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right)$ должна быть четная. Докажем это:

   $(\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right))\bmod{2} = (\varepsilon_p\left({b_{i_1}}\right)+\dots+\varepsilon_p\left({b_{i_t}}\right))\bmod{2} = {\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\varepsilon\left({b_{i_t}}\right) = 0$

2. $x^2 \equiv y^2\pmod{n}$ следует из того, что:

   $x^2 = b_{i_1}^2 \dots b_{i_t}^2 \equiv \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}\pmod{n}$

   $y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}$

Пример

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

$L(18638) = 194,174...$

$M = 13,934...$

$\Beta = \left\{ 2, 3, 5, 7, 11, 13 \right\}$

Все найденные числа $b$ с соответствующими векторами $\vec{\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

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

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

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

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

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

$u = (86660, 89755) = 3095$

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

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

Вычислительная сложность ^[5]

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

$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{M}{\ln{M}}$, и что $u = \frac{\ln{n}}{\ln{M}}$, после упрощения получаем

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

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

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

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

Дополнительные стратегии ^[6]

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

Стратегия LP

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

Алгоритм

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

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

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

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

Теоретическая оценка сложности алгоритма Диксона с применением LP стратегии остается прежней

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

Стратегия EAS

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

Алгоритм

Выбираются фиксированные $0 < k, l, m < 1$. В алгоритме Диксона $a$ факторизуется пробными делениями на $p < M = L\left({n}\right)^{\frac{1}{2}}$. В стратегии EAS выбирается $M = L\left({n}\right)^{k}$ и число сначала факторизуется пробными делениями на $p < M^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\left(z \cdot \ln^2{z} \cdot \ln^2{t}\right)$.^[7]

Алгоритм

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

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

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

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

Примечания

1. ↑ Ишмухаметов, 2011, с. 115
2. ↑ Dixon, J. D. (1981). «Asymptotically fast factorization of integers». Math. Comp. 36 (153): 255–260. DOI:10.1090/S0025-5718-1981-0595059-1.
3. ↑ Черемушкин, 2002, с. 77-79
4. ↑ Василенко, 2001, с. 79
5. ↑ Черемушкин, 2002, с. 79-80
6. ↑ Василенко, 2001, с. 81-83
7. ↑ Черемушкин, 2002, с. 74-75

Литература

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