Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и
Метод Диксона является обобщением метода Ферма.
История В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению , искать пары чисел, удовлетворяющих более общему уравнению . Крайчик заметил несколько полезных для решения фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод факторизации, использующий идеи Крайтчика, и рассчитал его вычислительную сложность.
Описание алгоритма
Составить факторную базу , состоящую из всех простых чисел , где . Выбрать случайное Вычислить . Проверить число на гладкость пробными делениями. Если является -гладким числом, то есть , следует запомнить вектора и :
.
Повторять процедуру генерации чисел до тех пор, пока не будет найдено -гладких чисел . Методом Гаусса найти линейную зависимость среди векторов :
и положить:
.
Проверить . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
Пример Факторизуем число .
Все найденные числа с соответствующими векторами записываем в таблицу.
337238141502004305390101210519965100006009802012006701250030008173920424002086021560301210 Решая линейную систему уравнений, получаем, что . Тогда
Следовательно,
. Получилось разложение
Вычислительная сложность Обозначим через количество целых чисел таких, что и является -гладким числом. Из теоремы де Брёйна — Эрдёша , где . Значит, каждое -гладкое число будет в среднем попадаться с попыток. Для проверки, является ли число -гладким, необходимо выполнить делений. По алгоритму необходимо найти -гладкое число. Значит, вычислительная сложность поиска чисел . Вычислительная сложность метода Гаусса из уравнений . Следовательно, суммарная сложность алгоритма Диксона . Учитывая, что количество простых чисел меньше оценивается формулой , и что , после упрощения получаем . выбирается таким образом, чтобы было минимально. Тогда подставляя , получаем
.
Это оценка, сделанная Диксоном. Оценка трудоёмкости алгоритма Диксона, сделанная Померанцем, дает .
Дополнительные стратегии Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.
Стратегия LP Стратегия LP (Large Prime variation) использует большие простые числа для ускорения процедуры генерации чисел .
Алгоритм Пусть найденное в пункте 4 число не является -гладким. Тогда его можно представить , где не делится на числа из факторной базы. Очевидно, что . Если дополнительно выполняется , то s — простое и мы включаем его в факторную базу. Это позволяет найти дополнительные -гладкие числа, но увеличивает количество необходимых гладких чисел на 1. Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть из факторной базы. Если же, например, таких чисел два и , то их нужно вычеркнуть и добавить число . Показатель войдет в разложение в четной степени и будет отсутствовать в системе линейных уравнений.
Вариация стратегии Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.
Вычислительная сложность Теоретическая оценка сложности алгоритма с применением LP стратегии, сделанная Померанцем, не отличается от оценки исходного варианта алгоритма Диксона: .
Стратегия EAS Стратегия EAS (раннего обрыва) исключает некоторые из рассмотрения, не доводя проверку на гладкость до конца.
Алгоритм Выбираются фиксированные . В алгоритме Диксона факторизуется пробными делениями на . В стратегии EAS выбирается и число сначала факторизуется пробными делениями на , и если после разложения неразложенная часть остается больше, чем , то данное отбрасывается.
Вариация стратегии Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности и убывающей последовательности .
Вычислительная сложность Алгоритм Диксона с применением стратегии EAS при оценивается .
Стратегия PS Стратегия PS использует алгоритм Полларда-Штрассена, который для и находит минимальный простой делитель числа НОД за .
Алгоритм Выбирается фиксированное . В алгоритме Диксона факторизуется пробными делениями на . В стратегии PS выбирается . Полагаем . Применяем алгоритм Полларда-Штрассена, выбирая за неразложенную часть, получим разложение .
Вычислительная сложность Сложность алгоритма Диксона со стратегией PS минимальна при и равна .
Примечания
Литература
Категория:Алгоритмы факторизации