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

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

История

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

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

 Составить факторную базу \Beta={p1,p2,…,ph}$\text{Beta}=\left\{p_1,p_2,\dots ,p_h\right\}$, состоящую из всех простых чисел p<=M=L(n)12$p<=M=L{\left(n\right)}^{\frac{1}{2}}$, где L(n)=exp(lnn⋅lnlnn−−−−−−−−−√)$L\left(n\right)=\exp \left(\sqrt{\ln n\cdot \ln \ln n}\right)$.
 Выбрать случайное $b, \sqrt{n} Вычислить a=b2modn$a=b^{2}modn$.
 Проверить число a$a$ на гладкость пробными делениями. Если a$a$ является \Beta$\text{Beta}$-гладким числом, то есть a=∏p\isin\Betapαp(b)$a=\prod _{p\text{isin}\text{Beta}}{p}^{{\alpha }_p\left(b\right)}$, следует запомнить вектора α⃗ (b)$\overrightarrow{\alpha }\left(b\right)$ и ε⃗ (b)$\overrightarrow{\epsilon }\left(b\right)$:
 
  α⃗ (b)=(αp1(b),…,αph(b))$\overrightarrow{\alpha }\left(b\right)=\left({\alpha }_{p_1}\left(b\right),\dots ,{\alpha }_{p_h}\left(b\right)\right)$
 ε⃗ (b)=(αp1(b)mod2,…,αph(b)mod2)$\overrightarrow{\epsilon }\left(b\right)=\left({\alpha }_{p_1}\left(b\right)mod2,\dots ,{\alpha }_{p_h}\left(b\right)mod2\right)$.
  Повторять процедуру генерации чисел b$b$ до тех пор, пока не будет найдено h+1$h+1$ \Beta$\text{Beta}$-гладких чисел b1,...,bh+1$b_1,...,b_{h+1}$.
 Методом Гаусса найти линейную зависимость среди векторов ε⃗ (b1),…,ε⃗ (bh+1)$\overrightarrow{\epsilon }\left(b_1\right),\dots ,\overrightarrow{\epsilon }\left(b_{h+1}\right)$:
 
  ε⃗ (bi1)⊕⋯⊕ε⃗ (bit)=0⃗ ,1⩽t⩽m$\overrightarrow{\epsilon }\left(b_{i_1}\right)\oplus \cdots \oplus \overrightarrow{\epsilon }\left(b_{i_t}\right)=\overrightarrow{0},1⩽t⩽m$
  и положить:
 
  x=bi1…bitmodn$x=b_{i_1}\dots b_{i_t}modn$
 y=∏p\isin\Betap(αp(bi1)+⋯+αp(bit))2modn$y=\prod _{p\text{isin}\text{Beta}}{p}^{\frac{\left({\alpha }_p\left(b_{i_1}\right)+\cdots +{\alpha }_p\left(b_{i_t}\right)\right)}{2}}modn$.
  Проверить x≡±y(modn)$x\equiv \pm y(\mathrm{mod}n)$. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
 
  n=u⋅v,u=(x+y,n),v=(x−y,n).$n=u\cdot v,u=\left(x+y,n\right),v=\left(x-y,n\right).$
  \{right)+\{dots+\{alpha\_p\{left(\{b\_\{i\_t\}\}\{right) должна быть четная. Докажем это:
 
  (αp(bi1)+⋯+αp(bit))mod2=(εp(bi1)+⋯+εp(bit))mod2=ε(bi1)⊕⋯⊕ε(bit)=0$({\alpha }_p\left(b_{i_1}\right)+\cdots +{\alpha }_p\left(b_{i_t}\right))mod2=({\epsilon }_p\left(b_{i_1}\right)+\cdots +{\epsilon }_p\left(b_{i_t}\right))mod2=\epsilon \left(b_{i_1}\right)\oplus \cdots \oplus \epsilon \left(b_{i_t}\right)=0$
  x2≡y2(modn)$x^2\equiv y^2(\mathrm{mod}n)$ следует из того, что:
 
  x2=b2i1…b2it≡∏p\isin\Betapαp(bi1)+⋯+αp(bit)(modn)$x^2=b_{i_1}^2\dots b_{i_t}^2\equiv \prod _{p\text{isin}\text{Beta}}{p}^{{\alpha }_p\left(b_{i_1}\right)+\cdots +{\alpha }_p\left(b_{i_t}\right)}(\mathrm{mod}n)$
 y2=∏p\isin\Betapαp(bi1)+⋯+αp(bit)$y^2=\prod _{p\text{isin}\text{Beta}}{p}^{{\alpha }_p\left(b_{i_1}\right)+\cdots +{\alpha }_p\left(b_{i_t}\right)}$
  \}\}
 

Пример

 Факторизуем число n=89755$n=89755$.
 
  L(89755)=194,174...$L(89755)=194,\mathrm{174...}$
 M=13,934...$M=13,\mathrm{934...}$
 \Beta={2,3,5,7,11,13}$\text{Beta}=\{2,3,5,7,11,13\}$
  Все найденные числа b$b$ с соответствующими векторами α⃗ (b)$\overrightarrow{\alpha }(b)$ записываем в таблицу.
 

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

 Решая линейную систему уравнений получаем, что ε⃗ (337)⊕ε⃗ (519)=0⃗ $\overrightarrow{\epsilon }\left(337\right)\oplus \overrightarrow{\epsilon }\left(519\right)=\overrightarrow{0}$. Тогда
 
  x=337⋅519mod89755=85148$x=337\cdot 519mod89755=85148$
 y=23⋅33⋅71mod89755=1512$y=2^3\cdot 3^3\cdot 7^{1}mod89755=1512$
 85148≢±1512(mod89755)$85148\not\equiv \pm 1512(\mathrm{mod}89755)$
  Следовательно,
 
  u=(86660,89755)=3095$u=(86660,89755)=3095$
 v=(83636,89755)=29$v=(83636,89755)=29$.
  Получилось разложение 89755=3095⋅29$89755=3095\cdot 29$
 

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

 Обозначим через Ψ(n,M)$\mathrm{\Psi }(n,M)$ количество целых чисел a$a$ таких, что 1<a⩽n$1<a⩽n$ и a$a$ является \Beta$\text{Beta}$-гладким числом, где \Beta={p:p<M}$\text{Beta}=\{p:p<M\}$. Из теоремы де Брёйна — Эрдёша Ψ(n,M)=n⋅u−u$\mathrm{\Psi }(n,M)=n\cdot u^{-u}$, где u=lnnlnM$u=\frac{\ln n}{\ln M}$. Значит, каждое \Beta$\text{Beta}$-гладкое число будет в среднем попадаться с uu$u^u$ попыток. Для проверки, является ли число \Beta$\text{Beta}$-гладким, необходимо выполнить h$h$ делений. По алгоритму необходимо найти h+1$h+1$ \Beta$\text{Beta}$-гладкое число. Значит, вычислительная сложность поиска чисел
 
  T1=O(uu⋅h2)$T_1=O\left(u^u\cdot h^2\right)$.
  Вычислительная сложность метода Гаусса из h$h$ уравнений
 
  T2=O(h3)$T_2=O\left(h^3\right)$.
  Следовательно, суммарная сложность алгоритма Диксона
 
  T=T1+T2=O(uu⋅h2+h3)$T=T_1+T_2=O\left(u^u\cdot h^2+h^3\right)$.
  Учитывая, что количество простых чисел меньше M$M$ оценивается формулой h=MlnM$h=\frac{M}{\ln M}$, и что u=lnnlnM$u=\frac{\ln n}{\ln M}$, после упрощения получаем
 
  T=O(exp(lnn⋅lnlnnlnM+lnM))$T=O(exp(\frac{\ln n\cdot \ln \ln n}{\ln M}+\ln M))$.
  M$M$ выбирается таким образом, чтобы T$T$ было минимально. Тогда подставляя L(n)=exp(lnn⋅lnlnn−−−−−−−−−√)$L\left(n\right)=\exp \left(\sqrt{\ln n\cdot \ln \ln n}\right)$, получаем
 
  M=L(n)12$M=L{\left(n\right)}^{\frac{1}{2}}$
 T=O(L(n)2)$T=O\left({L\left(n\right)}^2\right)$.
 

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

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

Стратегия LP

 Стратегия LP использует большие простые числа для ускорения процедуры генерации чисел b$b$.
 
agraphАлгоритм
 Пусть найденное в пункте 4 число a$a$ не является \Beta$\text{Beta}$-гладким. Тогда его можно представить a=s⋅∏p\isin\Betapαp(b)$a=s\cdot \prod _{p\text{isin}\text{Beta}}{p}^{{\alpha }_p\left(b\right)}$, где s$s$ не делится на числа из факторной базы. Очевидно, что s>M$s>M$. Если дополнительно выполняется s<M2$s<M^2$, то s — простое и мы включаем его в факторную базу. Это позволяет найти дополнительные \Beta$\text{Beta}$-гладкие числа, но увеличивает количество необходимых гладких чисел на 1. Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого s$s$ входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть s$s$ из факторной базы. Если же, например, таких чисел два b1$b_1$ и b2$b_2$, то их нужно вычеркнуть и добавить число b=b1⋅b2$b=b_1\cdot b_2$. Показатель s$s$ войдет в разложение b2modn$b^{2}modn$ в четной степени и будет отсутствовать в системе линейных уравнений.
 
agraphВариация стратегии
 Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.
 
agraphВычислительная сложность
 Теоретическая оценка сложности алгоритма Диксона с применением LP стратегии остается прежней
 
  TLP=O(L(n)2)$T_{LP}=O\left({L\left(n\right)}^2\right)$.
 

Стратегия EAS

 Стратегия EAS (раннего обрыва) исключает некоторые b$b$ из рассмотрения, не доводя проверку a$a$ на гладкость до конца.
 
agraphАлгоритм
 Выбираются фиксированные 0<k,l,m<1$0<k,l,m<1$. В алгоритме Диксона a$a$ факторизуется пробными делениями на p<M=L(n)12$p<M=L{\left(n\right)}^{\frac{1}{2}}$. В стратегии EAS выбирается M=L(n)k$M=L{\left(n\right)}^k$ и число сначала факторизуется пробными делениями на p<Ml=L(n)kl$p<M^l=L{\left(n\right)}^{kl}$, и если после разложения неразложенная часть остается больше, чем n1−m$n^{1-m}$, то данное b$b$ отбрасывается.
 
agraphВариация стратегии
 Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности lj$l_j$ и и убывающей последовательности mj$m_j$.
 
agraphВычислительная сложность
 Алгоритм Диксона с применением стратегии EAS при k=27√,l=12,m=17$k=\sqrt{\frac{2}{7}},l=\frac{1}{2},m=\frac{1}{7}$ оценивается
 
  TEAS=O(L(n)72√)$T_{EAS}=O\left({L\left(n\right)}^{\sqrt{\frac{7}{2}}}\right)$.
 

Стратегия PS

 Стратегия PS использует алгоритм Полларда-Штрассена, который для z,t∈N$z,t\in \mathbb{N}$ и y=z2$y=z^2$ находит минимальный простой делитель числа НОД(t,y!)$(t,y!)$ за O(z⋅ln2z⋅ln2t)$O(z\cdot {\ln }^{2}z\cdot {\ln }^{2}t)$.
 
agraphАлгоритм
 Выбирается фиксированное 0<k<1$0<k<1$. В алгоритме Диксона a$a$ факторизуется пробными делениями на p<M=L(n)12$p<M=L{\left(n\right)}^{\frac{1}{2}}$. В стратегии PS выбирается M=L(n)k$M=L{\left(n\right)}^k$. Полагаем z=[L(n)k2]+1,y=z2⩾L(n)k,t=a$z=[L{\left(n\right)}^{\frac{k}{2}}]+1,y=z^2⩾L{\left(n\right)}^k,t=a$. Применяем алгоритм Полларда-Штрассена, выбирая за t$t$ неразложенную часть, получим разложение a$a$.
 
agraphВычислительная сложность
 Сложность алгоритма Диксона со стратегией PS минимальна при k=13√$k=\frac{1}{\sqrt{3}}$ и равна
 
  TPS=O(L(n)3√)$T_{PS}=O\left({L\left(n\right)}^{\sqrt{3}}\right)$.