Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и
Метод Диксона является обобщением метода Ферма.
В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению , искать пары чисел, удовлетворяющих более общему уравнению . Крайчик заметил несколько полезных для решения фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод факторизации, использующий идеи Крайтчика, и рассчитал его вычислительную сложность.[2]
- Составить факторную базу , состоящую из всех простых чисел , где .
- Выбрать случайное
- Вычислить .
- Проверить число на гладкость пробными делениями. Если является -гладким числом, то есть , следует запомнить вектора и :
- .
- Повторять процедуру генерации чисел до тех пор, пока не будет найдено -гладких чисел .
- Методом Гаусса найти линейную зависимость среди векторов :
и положить:
- .
- Проверить . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
Пример
Факторизуем число .
Все найденные числа с соответствующими векторами записываем в таблицу.
|
|
|
|
|
|
|
|
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], дает , в то время как изначальная оценка сложности, сделанная самим Диксоном, дает .
Дополнительные стратегии [7]
Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.
Стратегия LP
Стратегия LP (Large Prime variation) использует большие простые числа для ускорения процедуры генерации чисел .
Алгоритм
Пусть найденное в пункте 4 число не является -гладким. Тогда его можно представить , где не делится на числа из факторной базы.
Очевидно, что . Если дополнительно выполняется , то s — простое и мы включаем его в факторную базу. Это позволяет найти дополнительные -гладкие числа, но увеличивает количество необходимых гладких чисел на 1.
Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть из факторной базы. Если же, например, таких чисел два и , то их нужно вычеркнуть и добавить число . Показатель войдет в разложение в четной степени и будет отсутствовать в системе линейных уравнений.
Вариация стратегии
Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.
Вычислительная сложность
Теоретическая оценка сложности алгоритма с применением LP стратегии, сделанная Померанцем, не отличается от оценки исходного варианта алгоритма Диксона:
- .
Стратегия EAS
Стратегия EAS (раннего обрыва) исключает некоторые из рассмотрения, не доводя проверку на гладкость до конца.
Алгоритм
Выбираются фиксированные . В алгоритме Диксона факторизуется пробными делениями на . В стратегии EAS выбирается и число сначала факторизуется пробными делениями на , и если после разложения неразложенная часть остается больше, чем , то данное отбрасывается.
Вариация стратегии
Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности и убывающей последовательности .
Вычислительная сложность
Алгоритм Диксона с применением стратегии EAS при оценивается
- .
Стратегия PS
Стратегия PS использует алгоритм Полларда-Штрассена, который для и находит минимальный простой делитель числа НОД за .[8]
Алгоритм
Выбирается фиксированное . В алгоритме Диксона факторизуется пробными делениями на . В стратегии PS выбирается . Полагаем . Применяем алгоритм Полларда-Штрассена, выбирая за неразложенную часть, получим разложение .
Вычислительная сложность
Сложность алгоритма Диксона со стратегией PS минимальна при и равна
- .
Примечания
- ↑ Ишмухаметов, 2011, с. 115.
- ↑ Dixon, J. D.[англ.]. Asymptotically fast factorization of integers (англ.) // Math. Comp.[англ.] : journal. — 1981. — Vol. 36, no. 153. — P. 255—260. — doi:10.1090/S0025-5718-1981-0595059-1. — JSTOR 2007743.
- ↑ Черемушкин, 2001, с. 77-79.
- ↑ Василенко, 2003, с. 79.
- ↑ Черемушкин, 2001, с. 79-80.
- ↑ C. Pomerance. Analysis and comparison of some integer factoring algorithms (англ.) // H. W. Lenstra and R. Tijdeman, Eds., Computational Methods in Number Theory, Math Centre Tracts —Part 1. Math Centrum, Amsterdam : Статья. — 1982. — С. 89-139. Архивировано 6 ноября 2021 года.
- ↑ Василенко, 2003, с. 81-83.
- ↑ Черемушкин, 2001, с. 74-75.
Литература