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

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

Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и

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

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

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

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

  1. Составить факторную базу , состоящую из всех простых чисел , где .
  2. Выбрать случайное
  3. Вычислить .
  4. Проверить число на гладкость пробными делениями. Если является -гладким числом, то есть , следует запомнить вектора и :
    .
  5. Повторять процедуру генерации чисел до тех пор, пока не будет найдено -гладких чисел .
  6. Методом Гаусса найти линейную зависимость среди векторов :
    и положить:
    .
  7. Проверить . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:


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

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

Все найденные числа с соответствующими векторами записываем в таблицу.

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

Решая линейную систему уравнений получаем, что . Тогда

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

.

Получилось разложение

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

Обозначим через количество целых чисел таких, что и является -гладким числом, где . Из теоремы де Брёйна — Эрдёша , где . Значит, каждое -гладкое число будет в среднем попадаться с попыток. Для проверки, является ли число -гладким, необходимо выполнить делений. По алгоритму необходимо найти -гладкое число. Значит, вычислительная сложность поиска чисел

.

Вычислительная сложность метода Гаусса из уравнений

.

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

.

Учитывая, что количество простых чисел меньше оценивается формулой , и что , после упрощения получаем

.

выбирается таким образом, чтобы было минимально. Тогда подставляя , получаем

.

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

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

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

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

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

Пусть найденное в пункте 4 число не является -гладким. Тогда его можно представить , где не делится на числа из факторной базы. Очевидно, что . Если дополнительно выполняется , то s - простое и мы включаем его в факторную базу. Это позволяет найти дополнительные -гладкие числа, но увеличивает количество необходимых гладких чисел на 1. Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть из факторной базы. Если же, например, таких чисел два и , то их нужно вычеркнуть и добавить число . Показатель войдет в разложение в четной степени и будет отсутствовать в системе линейных уравнений.

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

Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.

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

Теоретическая оценка сложности алгоритма Диксона с применением LP стратегии остается прежней

.

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

Стратегия EAS (раннего обрыва) исключает некоторые из рассмотрения, не доводя проверку на гладкость до конца.

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

Выбираются фиксированные . В алгоритме Диксона факторизуется пробными делениями на . В стратегии EAS выбирается и число сначала факторизуется пробными делениями на , и если после разложения неразложенная часть остается больше, чем , то данное отбрасывается.

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

Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности и и убывающей последовательности .

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

Алгоритм Диксона с применением стратегии EAS при оценивается

.

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

Стратегия PS использует алгоритм Полларда-Штрассена, который для и находит минимальный простой делитель числа НОД за .[7]

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

Выбирается фиксированное . В алгоритме Диксона факторизуется пробными делениями на . В стратегии PS выбирается . Полагаем . Применяем алгоритм Полларда-Штрассена, выбирая за неразложенную часть, получим разложение .

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

Сложность алгоритма Диксона со стратегией PS минимальна при и равна

.

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

  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 с.