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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История [1][править | править вики-текст]

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

Описание алгоритма [3][править | править вики-текст]

  1. Составить факторную базу \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 \ln{\ln{n}}}}\right)}.
  2. Выбрать случайное b, \sqrt{n}<b<n
  3. Вычислить a = b^2\bmod{n}.
  4. Проверить число a на гладкость пробными делениями. Если a является \Beta-гладким числом, то есть a = \prod_{p\isin \Beta}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 \Beta-гладких чисел 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\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 \pm y \pmod{n}. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
    n=u\cdot v, u=\left({x+y,n}\right), v=\left({x-y,n}\right).

Пример[править | править вики-текст]

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

L(18638) = 194,174...
M = 13,934...
\Beta = \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 = (86660, 89755) = 3095
v = (83636, 89755) = 29.

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

Вычислительная сложность [5][править | править вики-текст]

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

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{M}{\ln{M}}, и что u = \frac{\ln{n}}{\ln{M}}, после упрощения получаем

T = O\left( exp(\frac{\ln{n} \cdot \ln{\ln{n}}}{\ln{M}} + \ln{M})\right).

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

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

Дополнительные стратегии [6][править | править вики-текст]

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

Стратегия LP[править | править вики-текст]

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

Алгоритм[править | править вики-текст]

Пусть найденное в пункте 4 число a не является \Beta-гладким. Тогда его можно представить a = s \cdot \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}, где s не делится на числа из факторной базы. Очевидно, что s > M. Если дополнительно выполняется s < M^2, то s - простое и мы включаем его в факторную базу. Это позволяет найти дополнительные \Beta-гладкие числа, но увеличивает количество необходимых гладких чисел на 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 < M = L\left({n}\right)^{\frac{1}{2}}. В стратегии EAS выбирается M = L\left({n}\right)^{k} и число сначала факторизуется пробными делениями на p < M^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).[7]

Алгоритм[править | править вики-текст]

Выбирается фиксированное 0 < k < 1. В алгоритме Диксона a факторизуется пробными делениями на p < M = L\left({n}\right)^{\frac{1}{2}}. В стратегии PS выбирается M = 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_{EAS} = O\left({L\left({n}\right)}^{\sqrt{3}}\right).

Примечания[править | править вики-текст]

  1. Ишмухаметов, 2011, с. 115
  2. Dixon, J. D. (1981). «Asymptotically fast factorization of integers». Math. Comp. 36 (153): 255–260. DOI:10.1090/S0025-5718-1981-0595059-1.
  3. Черемушкин, 2002, с. 77-79
  4. Василенко, 2001, с. 79
  5. Черемушкин, 2002, с. 79-80
  6. Василенко, 2001, с. 81-83
  7. Черемушкин, 2002, с. 74-75

Литература[править | править вики-текст]

  1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 78-83. — 328 с. — ISBN 5-94057-103-4
  2. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2001. — С. 74-80. — 104 с. — ISBN 5-94057-060-7
  3. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань: Казан. ун., 2011. — С. 115-117. — 190 с.