Алгоритм Диксона (Glikjnmb :ntvkug)

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

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

История

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

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

1. Составить факторную базу $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)}$.
2. Выбрать случайное $b,{\sqrt {n}}<b<n$
3. Вычислить $a=b^{2}{\bmod {n}}$.
4. Проверить число $a$ на гладкость пробными делениями. Если $a$ является $\mathrm {B}$-гладким числом, то есть $a=\prod _{p\in \mathrm {B} }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$ $\mathrm {B}$-гладких чисел $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\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. Проверить $x\equiv \pm y{\pmod {n}}$. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

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

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

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\in \mathrm {B} }p^{\alpha _{p}\left({b_{i_{1}}}\right)+\dots +\alpha _{p}\left({b_{i_{t}}}\right)}{\pmod {n}}$

   $y^{2}=\prod _{p\in \mathrm {B} }p^{\alpha _{p}\left({b_{i_{1}}}\right)+\dots +\alpha _{p}\left({b_{i_{t}}}\right)}$

Пример

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

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

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

$P=\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=gcd(86660,89755)=3095$

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

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

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

Обозначим через $\Psi (n,\mathrm {B} )$ количество целых чисел $a$ таких, что $1<a\leqslant n$ и $a$ является $\mathrm {B}$-гладким числом. Из теоремы де Брёйна — Эрдёша $\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\left(exp({\frac {\ln {n}\cdot \ln {\ln {n}}}{\ln {\mathrm {B} }}}+2\ln {\mathrm {B} })\right)$.

$\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)$.

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

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

Стратегия 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}{\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<\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\left(z\cdot \ln ^{2}{z}\cdot \ln ^{2}{t}\right)$.

Алгоритм

Выбирается фиксированное $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}\geqslant 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)$.

Литература

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