WikiSort.ru - Не сортированное

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

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

История ^[1]

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

Описание алгоритма ^[3]

1. Составить факторную базу ${\displaystyle \mathrm {B} =\left\{{p_{1},p_{2},\dots ,p_{h}}\right\}}$ , состоящую из всех простых чисел ${\displaystyle p<=M=L\left({n}\right)^{\frac {1}{2}}}$ , где ${\displaystyle L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n}}}}\right)}}$ .
2. Выбрать случайное ${\displaystyle b,{\sqrt {n}}<b<n}$
3. Вычислить ${\displaystyle a=b^{2}{\bmod {n}}}$ .
4. Проверить число ${\displaystyle a}$ на гладкость пробными делениями. Если ${\displaystyle a}$ является ${\displaystyle \mathrm {B} }$ -гладким числом, то есть ${\displaystyle a=\prod _{p\in \mathrm {B} }p^{\alpha _{p}\left({b}\right)}}$ , следует запомнить вектора ${\displaystyle {\vec {\alpha }}\left({b}\right)}$ и ${\displaystyle {\vec {\varepsilon }}\left({b}\right)}$ :

   ${\displaystyle {\vec {\alpha }}\left({b}\right)=\left({\alpha _{p_{1}}\left({b}\right),\dots ,\alpha _{p_{h}}\left({b}\right)}\right)}$

   ${\displaystyle {\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. Повторять процедуру генерации чисел ${\displaystyle b}$ до тех пор, пока не будет найдено ${\displaystyle h+1}$ ${\displaystyle \mathrm {B} }$ -гладких чисел ${\displaystyle b_{1},...,b_{h+1}}$ .
6. Методом Гаусса найти линейную зависимость среди векторов ${\displaystyle {\vec {\varepsilon }}\left({b_{1}}\right),\dots ,{\vec {\varepsilon }}\left({b_{h+1}}\right)}$ :

   ${\displaystyle {\vec {\varepsilon }}\left({b_{i_{1}}}\right)\oplus \dots \oplus {\vec {\varepsilon }}\left({b_{i_{t}}}\right)={\vec {0}},1\leqslant t\leqslant m}$

   и положить:

   ${\displaystyle x=b_{i_{1}}\dots b_{i_{t}}{\bmod {n}}}$

   ${\displaystyle 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. Проверить ${\displaystyle x\equiv \pm y{\pmod {n}}}$ . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

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

Пример

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

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

${\displaystyle M=13,934...}$

${\displaystyle \mathrm {B} =\left\{2,3,5,7,11,13\right\}}$

Все найденные числа ${\displaystyle b}$ с соответствующими векторами ${\displaystyle {\vec {\alpha }}(b)}$ записываем в таблицу.

${\displaystyle b}$	${\displaystyle a}$	${\displaystyle \alpha _{2}\left({b}\right)}$	${\displaystyle \alpha _{3}\left({b}\right)}$	${\displaystyle \alpha _{5}\left({b}\right)}$	${\displaystyle \alpha _{7}\left({b}\right)}$	${\displaystyle \alpha _{11}\left({b}\right)}$	${\displaystyle \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

Решая линейную систему уравнений, получаем, что ${\displaystyle {\vec {\varepsilon }}\left(337\right)\oplus {\vec {\varepsilon }}\left(519\right)={\vec {0}}}$ . Тогда

${\displaystyle x=337\cdot 519{\bmod {89755}}=85148}$

${\displaystyle y=2^{3}\cdot 3^{3}\cdot 7^{1}{\bmod {89755}}=1512}$

${\displaystyle 85148\not \equiv \pm 1512{\pmod {89755}}}$

Следовательно,

${\displaystyle u=gcd(86660,89755)=3095}$

${\displaystyle v=gcd(83636,89755)=29}$ .

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

Вычислительная сложность ^[5]

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

${\displaystyle T_{1}=O\left({u^{u}\cdot h^{2}}\right)}$ .

Вычислительная сложность метода Гаусса из ${\displaystyle h}$ уравнений

${\displaystyle T_{2}=O\left({h^{3}}\right)}$ .

Следовательно, суммарная сложность алгоритма Диксона

${\displaystyle T=T_{1}+T_{2}=O\left({u^{u}\cdot h^{2}+h^{3}}\right)}$ .

Учитывая, что количество простых чисел меньше ${\displaystyle M}$ оценивается формулой ${\displaystyle h={\frac {M}{\ln {M}}}}$ , и что ${\displaystyle u={\frac {\ln {n}}{\ln {M}}}}$ , после упрощения получаем

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

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

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

${\displaystyle T=O\left({L\left({n}\right)}^{2}\right)}$ .

Дополнительные стратегии ^[6]

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

Примечания

Литература

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