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

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

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

История Править

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

Описание алгоритма Править

1. Составить факторную базу $\mathrm{B}=\left\{p_1,p_2,\dots <!--\; \dots \; -->,p_h\right\}$$\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 <!--\; \cdot \; -->\ln <!--\; \; -->\ln <!--\; \; -->n}\right)$$L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}$ .
2. Выбрать случайное $b, \sqrt{n}<b<n$ 
3. Вычислить $a=b^{2}modn$$a = b^2\bmod{n}$ .
4. Проверить число $a$$a$  на гладкость пробными делениями. Если $a$$a$  является $\mathrm{B}$$\mathrm{B}$ -гладким числом, то есть $a=\underset{p\in <!--\; \in \; -->\mathrm{B}}{\prod <!--\; \prod \; -->}{p}^{{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b\right)}$$a = \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}$ , следует запомнить вектора $\stackrel{\to <!--\; \to \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}\left(b\right)$$\vec{\alpha}\left({b}\right)$  и $\stackrel{\to <!--\; \to \; -->}{\mathrm{\epsilon <!--\; \epsilon \; -->}}\left(b\right)$$\vec{\varepsilon}\left({b}\right)$ :

   $\stackrel{\to <!--\; \to \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}\left(b\right)=\left({\mathrm{\alpha <!--\; \alpha \; -->}}_{p_1}\left(b\right),\dots <!--\; \dots \; -->,{\mathrm{\alpha <!--\; \alpha \; -->}}_{p_h}\left(b\right)\right)$$\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\right)}\right)$ 

   $\stackrel{\to <!--\; \to \; -->}{\mathrm{\epsilon <!--\; \epsilon \; -->}}\left(b\right)=\left({\mathrm{\alpha <!--\; \alpha \; -->}}_{p_1}\left(b\right)mod2,\dots <!--\; \dots \; -->,{\mathrm{\alpha <!--\; \alpha \; -->}}_{p_h}\left(b\right)mod2\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$$b$  до тех пор, пока не будет найдено $h+1$$h+1$  $\mathrm{B}$$\mathrm{B}$ -гладких чисел $b_1,...,b_{h+1}$$b_1,...,b_{h+1}$ .
6. Методом Гаусса найти линейную зависимость среди векторов $\stackrel{\to <!--\; \to \; -->}{\mathrm{\epsilon <!--\; \epsilon \; -->}}\left(b_1\right),\dots <!--\; \dots \; -->,\stackrel{\to <!--\; \to \; -->}{\mathrm{\epsilon <!--\; \epsilon \; -->}}\left(b_{h+1}\right)$$\vec{\varepsilon}\left({b_1}\right), \dots, \vec{\varepsilon}\left({b_{h+1}}\right)$ :

   $\stackrel{\to <!--\; \to \; -->}{\mathrm{\epsilon <!--\; \epsilon \; -->}}\left(b_{i_1}\right)\oplus <!--\; \oplus \; -->\cdots <!--\; \cdots \; -->\oplus <!--\; \oplus \; -->\stackrel{\to <!--\; \to \; -->}{\mathrm{\epsilon <!--\; \epsilon \; -->}}\left(b_{i_t}\right)=\stackrel{\to <!--\; \to \; -->}{0},1⩽<!--\; ⩽\; -->t⩽<!--\; ⩽\; -->m$$\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 <!--\; \dots \; -->b_{i_t}modn$$x=b_{i_1} \dots b_{i_t}\bmod{n}$ 

   $y=\underset{p\in <!--\; \in \; -->\mathrm{B}}{\prod <!--\; \prod \; -->}{p}^{\frac{\left({\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_1}\right)+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_t}\right)\right)}{2}}modn$$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 <!--\; \equiv \; -->\pm <!--\; \pm \; -->y(\mathrm{mod}n)$$x \equiv \pm y \pmod{n}$ . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

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

Доказательство корректности

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

   $({\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_1}\right)+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_t}\right))mod2=({\mathrm{\epsilon <!--\; \epsilon \; -->}}_p\left(b_{i_1}\right)+\cdots <!--\; \cdots \; -->+{\mathrm{\epsilon <!--\; \epsilon \; -->}}_p\left(b_{i_t}\right))mod2=\mathrm{\epsilon <!--\; \epsilon \; -->}\left(b_{i_1}\right)\oplus <!--\; \oplus \; -->\cdots <!--\; \cdots \; -->\oplus <!--\; \oplus \; -->\mathrm{\epsilon <!--\; \epsilon \; -->}\left(b_{i_t}\right)=0$$(\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 <!--\; \equiv \; -->y^2(\mathrm{mod}n)$$x^2 \equiv y^2\pmod{n}$  следует из того, что:

   $x^2=b_{i_1}^2\dots <!--\; \dots \; -->b_{i_t}^2\equiv <!--\; \equiv \; -->\underset{p\in <!--\; \in \; -->\mathrm{B}}{\prod <!--\; \prod \; -->}{p}^{{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_1}\right)+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_t}\right)}(\mathrm{mod}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=\underset{p\in <!--\; \in \; -->\mathrm{B}}{\prod <!--\; \prod \; -->}{p}^{{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_1}\right)+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_p\left(b_{i_t}\right)}$$y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}$ 

ПримерПравить

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

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

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

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

Все найденные числа $b$$b$  с соответствующими векторами $\stackrel{\to <!--\; \to \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}(b)$${\vec {\alpha }}(b)$  записываем в таблицу.

$b$$b$	$a$$a$	${\mathrm{\alpha <!--\; \alpha \; -->}}_2\left(b\right)$$\alpha_2\left({b}\right)$	${\mathrm{\alpha <!--\; \alpha \; -->}}_3\left(b\right)$$\alpha_3\left({b}\right)$	${\mathrm{\alpha <!--\; \alpha \; -->}}_5\left(b\right)$$\alpha_5\left({b}\right)$	${\mathrm{\alpha <!--\; \alpha \; -->}}_7\left(b\right)$$\alpha_7\left({b}\right)$	${\mathrm{\alpha <!--\; \alpha \; -->}}_{11}\left(b\right)$$\alpha_{11}\left({b}\right)$	${\mathrm{\alpha <!--\; \alpha \; -->}}_{13}\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

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

$x=337\cdot <!--\; \cdot \; -->519mod89755=85148$$x = 337 \cdot 519 \bmod{89755}= 85148$ 

$y=2^3\cdot <!--\; \cdot \; -->3^3\cdot <!--\; \cdot \; -->7^{1}mod89755=1512$$y = 2^3 \cdot 3^3 \cdot 7^1 \bmod{89755} = 1512$ 

$85148\not\equiv \pm <!--\; \pm \; -->1512(\mathrm{mod}89755)$$85148 \not\equiv \pm 1512 \pmod{89755}$ 

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

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

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

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

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

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

$T_1=O\left(u^u\cdot <!--\; \cdot \; -->h^2\right)$$T_1 = O\left({u^{u}\cdot h^{2}}\right)$ .

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

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

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

$T=T_1+T_2=O\left(u^u\cdot <!--\; \cdot \; -->h^2+h^3\right)$$T = T_1 + T_2 = O\left({u^{u}\cdot h^{2}+h^{3}}\right)$ .

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

$T=O\left(exp(\frac{\ln <!--\; \; -->n\cdot <!--\; \cdot \; -->\ln <!--\; \; -->\ln <!--\; \; -->n}{\ln <!--\; \; -->M}+2\ln <!--\; \; -->M)\right)$$T=O\left(exp({\frac {\ln {n}\cdot \ln {\ln {n}}}{\ln {M}}}+2\ln {M})\right)$ .

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

$M={\left(\frac{L\left(n\right)}{2}\right)}^{\frac{1}{2}}$$M=\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{\sqrt {2}}}\right)$ .

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

Дополнительные стратегии Править

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

Стратегия LPПравить

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

АлгоритмПравить

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

Вариация стратегииПравить

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

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

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

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

Стратегия EASПравить

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

АлгоритмПравить

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

Вариация стратегииПравить

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

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

Алгоритм Диксона с применением стратегии EAS при $k=\sqrt{\frac{2}{7}},l=\frac{1}{2},m=\frac{1}{7}$$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)$$T_{EAS} = O\left({L\left({n}\right)}^{\sqrt{\frac{7}{2}}}\right)$ .

Стратегия PSПравить

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

АлгоритмПравить

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

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

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

$T_{PS}=O\left({L\left(n\right)}^{\sqrt{3}}\right)$$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 с.