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

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

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

Предварительные вычисления

Пусть задано подмножество простых чисел $\Beta = \left\{ {p_1,p_2,\dots,p_h} \right\}$, называемое факторной базой.

Каждому $\Beta$-гладкому числу сопоставляется вектор показателей из разложения $\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\right)}\right)$, а также двоичный вектор, полученный из вектора $\vec{a}\left({b}\right)$ приведением всех его координат по модулю 2,

$\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\mod{2}, \dots, \alpha_{p_h}\left({b}\right)\mod{2}}\right)$.

Если теперь подобрать такое множество различных $\Beta$-гладких чисел $b_1,\dots,b_m$, что выполнится линейное соотношение

$\vec{\varepsilon}\left({b_1}\right)\oplus \cdots \oplus\vec{\varepsilon}\left({b_m}\right)=\vec{0},$

то для произведения $x=b_1\cdots b_m$ выполнится сравнение

$x^2\equiv y^2 \pmod{n},$

где $y$ определяется как

$y=\prod_{p \isin \Beta}p^{\left({ \vec{\alpha_p}\left({b_1}\right) + \dots +\vec{\alpha_p}\left({b_m}\right) }\right) \over{2}}.$

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

1. Выбирается случайное $~b, 1<b<n$ и вычисляется $~b^2\bmod{n}$.
2. Проверка, факторизуют ли числа из факторной базы $~b^2\bmod{n}$.
3. Если $~b^2 \bmod{n}$ является $\Beta$-гладким числом, то есть:

   $b^2 \equiv \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}\pmod{n},$

   следует запомнить $\vec{\alpha} \left({b}\right)$ и $\vec{\varepsilon} \left({b}\right)$. Повторять процедуру генерации чисел $~b$ до тех пор, пока не будет найдено $~m=h+1$ чисел чисел $~b_1,...,b_m$, являющихся $\Beta$-гладкими.
4. Найти линейную зависимость:

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

   и положить:

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

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

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

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

Среднюю временную арифметическую сложность алгоритма Диксона можно оценить выражением

$T=O_A \left({u^{u}\cdot h^{2}+h^{3}}\right)$,

где $O_A \left({h^3}\right)$ — сложность решения системы из $h+1$ линейных уравнений от $h$ неизвестных. В данном случае $h=\pi \left({M}\right)=\frac{M}{\ln{M}}$.

Возьмем в качестве $M$ величину $M=L\left({n}\right)^{\frac{1}{2}}$, где $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}$, тогда

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

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

Отсюда следует, что трудоемкость алгоритма Диксона оценивается следующим образом

$T=O_{A}\left({L\left({n}\right)^{2}+L\left({n}\right)^{\frac{3}{2}}}\right)=O\left({L\left({n}\right)}^{2}\right).$

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. 2003. Стр. 78-83.
• Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. 2002. Стр. 77-80.