Русская Википедия:Алгоритм Диксона
Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел <math>x</math> и <math>y</math> таких, что <math>x^2 \equiv y^2\pmod{n}</math> и <math>x \not\equiv \pm y\pmod{n}.</math>
Метод Диксона является обобщением метода Ферма.
История Шаблон:Sfn
В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению <math>x^2 - y^2 = n</math>, искать пары чисел, удовлетворяющих более общему уравнению <math>x^2 \equiv y^2\pmod{n}</math>. Крайчик заметил несколько полезных для решения фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод факторизации, использующий идеи Крайтчика, и рассчитал его вычислительную сложность.[1]
Описание алгоритма Шаблон:Sfn
- Составить факторную базу <math>\Beta = \left\{ {p_1,p_2,\dots,p_h} \right\}</math>, состоящую из всех простых чисел <math>p <= M = L\left({n}\right)^{\frac{1}{2}}</math>, где <math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}</math>.
- Выбрать случайное <math>b, \sqrt{n}<b<n</math>
- Вычислить <math>a = b^2\bmod{n}</math>.
- Проверить число <math>a</math> на гладкость пробными делениями. Если <math>a</math> является <math>\Beta</math>-гладким числом, то есть <math>a = \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}</math>, следует запомнить вектора <math>\vec{\alpha}\left({b}\right)</math> и <math>\vec{\varepsilon}\left({b}\right)</math>:
- <math>\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\right)}\right)</math>
- <math>\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left({b}\right)\bmod{2}}\right)</math>.
- Повторять процедуру генерации чисел <math>b</math> до тех пор, пока не будет найдено <math>h+1</math> <math>\Beta</math>-гладких чисел <math>b_1,...,b_{h+1}</math>.
- Методом Гаусса найти линейную зависимость среди векторов <math>\vec{\varepsilon}\left({b_1}\right), \dots, \vec{\varepsilon}\left({b_{h+1}}\right)</math>:
- <math>\vec{\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\vec{\varepsilon}\left({b_{i_t}}\right)=\vec{0}, 1 \leqslant t \leqslant m</math>
- <math>x=b_{i_1} \dots b_{i_t}\bmod{n}</math>
- <math>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}</math>.
- Проверить <math>x \equiv \pm y \pmod{n}</math>. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
- <math>n=u\cdot v, u=gcd\left({x+y,n}\right), v=gcd\left({x-y,n}\right).</math>
Шаблон:Hider\right)+\dots+\alpha_p\left({b_{i_t}}\right)</math> должна быть четная. Докажем это:
- <math>(\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</math>
- <math>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}</math>
- <math>y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}</math>
}}
Пример
Факторизуем число <math>n = 89755</math>.
- <math>L(89755) = 194,174...</math>
- <math>M = 13,934...</math>
- <math>\Beta = \left\{ 2, 3, 5, 7, 11, 13 \right\}</math>
Все найденные числа <math>b</math> с соответствующими векторами <math>\vec{\alpha}(b)</math> записываем в таблицу.
| <math>b</math> | <math>a</math> | <math>\alpha_2\left({b}\right)</math> | <math>\alpha_3\left({b}\right)</math> | <math>\alpha_5\left({b}\right)</math> | <math>\alpha_7\left({b}\right)</math> | <math>\alpha_{11}\left({b}\right)</math> | <math>\alpha_{13}\left({b}\right)</math> |
|---|---|---|---|---|---|---|---|
| 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 |
Решая линейную систему уравнений, получаем, что <math>\vec{\varepsilon}\left(337\right)\oplus\vec{\varepsilon}\left(519\right)=\vec{0}</math>. Тогда
- <math>x = 337 \cdot 519 \bmod{89755}= 85148</math>
- <math>y = 2^3 \cdot 3^3 \cdot 7^1 \bmod{89755} = 1512</math>
- <math>85148 \not\equiv \pm 1512 \pmod{89755}</math>
Следовательно,
- <math>u = gcd(86660, 89755) = 3095</math>
- <math>v = gcd(83636, 89755) = 29</math>.
Получилось разложение <math>89755 = 3095 \cdot 29</math>
Вычислительная сложность Шаблон:Sfn
Обозначим через <math>\Psi(n, M)</math> количество целых чисел <math>a</math> таких, что <math>1 < a \leqslant n</math> и <math>a</math> является <math>\Beta</math>-гладким числом, где <math>\Beta = \{p : p < M\}</math>. Из теоремы де Брёйна — Эрдёша <math>\Psi(n, M) = n \cdot u^{-u}</math>, где <math>u = \frac{\ln{n}}{\ln{M}}</math>. Значит, каждое <math>\Beta</math>-гладкое число будет в среднем попадаться с <math>u^u</math> попыток. Для проверки, является ли число <math>\Beta</math>-гладким, необходимо выполнить <math>h</math> делений. По алгоритму необходимо найти <math>h+1</math> <math>\Beta</math>-гладкое число. Значит, вычислительная сложность поиска чисел
- <math>T_1 = O\left({u^{u}\cdot h^{2}}\right)</math>.
Вычислительная сложность метода Гаусса из <math>h</math> уравнений
- <math>T_2 = O\left({h^3}\right)</math>.
Следовательно, суммарная сложность алгоритма Диксона
- <math>T = T_1 + T_2 = O\left({u^{u}\cdot h^{2}+h^{3}}\right)</math>.
Учитывая, что количество простых чисел меньше <math>M</math> оценивается формулой <math>h = \frac{M}{\ln{M}}</math>, и что <math>u = \frac{\ln{n}}{\ln{M}}</math>, после упрощения получаем
- <math>T = O\left( exp(\frac{\ln{n} \cdot \ln{\ln{n}}}{\ln{M}} + 2\ln{M})\right)</math>.
<math>M</math> выбирается таким образом, чтобы <math>T</math> было минимально. Тогда подставляя <math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}</math>, получаем
- <math>M=\left(\frac{L\left({n}\right)}{2}\right)^{\frac{1}{2}}</math>
- <math>T = O\left({L\left({n}\right)}^{2\sqrt{2}}\right)</math>.
Оценка, сделанная Померанцем на основании более строгой теоремы, чем теорема де Брёйна — Эрдеша[2], дает <math>T = O\left({L\left({n}\right)}^{2}\right)</math>, в то время как изначальная оценка сложности, сделанная самим Диксоном, дает <math>T = O\left({L\left({n}\right)}^{3\sqrt{2}}\right)</math>.
Дополнительные стратегии Шаблон:Sfn
Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.
Стратегия LP
Стратегия LP (Large Prime variation) использует большие простые числа для ускорения процедуры генерации чисел <math>b</math>.
Алгоритм
Пусть найденное в пункте 4 число <math>a</math> не является <math>\Beta</math>-гладким. Тогда его можно представить <math>a = s \cdot \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}</math>, где <math>s</math> не делится на числа из факторной базы. Очевидно, что <math>s > M</math>. Если дополнительно выполняется <math>s < M^2</math>, то s — простое и мы включаем его в факторную базу. Это позволяет найти дополнительные <math>\Beta</math>-гладкие числа, но увеличивает количество необходимых гладких чисел на 1. Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого <math>s</math> входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть <math>s</math> из факторной базы. Если же, например, таких чисел два <math>b_1</math> и <math>b_2</math>, то их нужно вычеркнуть и добавить число <math>b = b_1 \cdot b_2</math>. Показатель <math>s</math> войдет в разложение <math>b^2\bmod{n}</math> в четной степени и будет отсутствовать в системе линейных уравнений.
Вариация стратегии
Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.
Вычислительная сложность
Теоретическая оценка сложности алгоритма с применением LP стратегии, сделанная Померанцем, не отличается от оценки исходного варианта алгоритма Диксона:
- <math>T_{LP} = O\left({L\left({n}\right)}^{2}\right)</math>.
Стратегия EAS
Стратегия EAS (раннего обрыва) исключает некоторые <math>b</math> из рассмотрения, не доводя проверку <math>a</math> на гладкость до конца.
Алгоритм
Выбираются фиксированные <math>0 < k, l, m < 1</math>. В алгоритме Диксона <math>a</math> факторизуется пробными делениями на <math>p < M = L\left({n}\right)^{\frac{1}{2}}</math>. В стратегии EAS выбирается <math>M = L\left({n}\right)^{k}</math> и число сначала факторизуется пробными делениями на <math>p < M^l = L\left({n}\right)^{kl}</math>, и если после разложения неразложенная часть остается больше, чем <math>n^{1-m}</math>, то данное <math>b</math> отбрасывается.
Вариация стратегии
Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности <math>l_j</math> и убывающей последовательности <math>m_j</math>.
Вычислительная сложность
Алгоритм Диксона с применением стратегии EAS при <math>k = \sqrt{\frac{2}{7}}, l = \frac{1}{2}, m = \frac{1}{7}</math> оценивается
- <math>T_{EAS} = O\left({L\left({n}\right)}^{\sqrt{\frac{7}{2}}}\right)</math>.
Стратегия PS
Стратегия PS использует алгоритм Полларда-Штрассена, который для <math>z, t \in \mathbb{N}</math> и <math>y = z^2</math> находит минимальный простой делитель числа НОД<math>(t, y!)</math> за <math>O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\right)</math>.Шаблон:Sfn
Алгоритм
Выбирается фиксированное <math>0 < k < 1</math>. В алгоритме Диксона <math>a</math> факторизуется пробными делениями на <math>p < M = L\left({n}\right)^{\frac{1}{2}}</math>. В стратегии PS выбирается <math>M = L\left({n}\right)^{k}</math>. Полагаем <math>z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = a</math>. Применяем алгоритм Полларда-Штрассена, выбирая за <math>t</math> неразложенную часть, получим разложение <math>a</math>.
Вычислительная сложность
Сложность алгоритма Диксона со стратегией PS минимальна при <math>k = \frac{1}{\sqrt{3}}</math> и равна
- <math>T_{PS} = O\left({L\left({n}\right)}^{\sqrt{3}}\right)</math>.
Примечания
Литература
