10-08-2023
() — метод Уильямса — метод факторизации чисел с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель числа . Аналогичен () — методу Полларда, но использует разложение на множители числа . Имеет хорошие показатели производительности только в случае, когда легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев[1].
Для дальнейших выкладок нам понадобится ввести последовательности чисел Люка и перечислить некоторые их свойства.
Пусть и — некоторые фиксированные целые числа. Последовательности чисел Люка определяются как[1]:
Пусть также
Последовательности имеют следующие свойства:
Для доказательства данных свойств рассмотрим явные формулы последовательности чисел Люка:
и
где и — корни характеристического многочлена
Используя явные формулы и теорему Виетта:
получаем выражения и
Далее выделяем ещё одно свойство:
Если НОД и то: и откуда
И, наконец, формулируем теорему:
Доказательство данной теоремы трудоёмкое, и его можно найти в книге Д. Г. Лемера[2].
Пусть — простой делитель факторизуемого числа , и выполнено разложение:
где — простые числа.
Пусть
Введём число где степени выбираются таким образом, что
Тогда [1]
Далее, согласно теореме если НОД то
И, следовательно, НОД то есть найден делитель искомого числа [1].
Стоит обратить внимание, что числа не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как то по свойству (2) Далее воспользуемся свойством (6) и получим:
Таким образом, мы без потери общности можем утверждать, что [1]
Далее пользуемся теоремой из которой делаем вывод, что
И, следовательно, [1]
Теперь выбираем некоторое число такое, что НОД
Обозначаем:
Окончательно, нужно найти НОД[1]
Для поиска поступаем следующим образом[1]:
1) раскладываем в двоичный вид: где .
2) вводим последовательность натуральных чисел . При этом ;
3) ищем пары значений по следующему правилу:
4) значения ищутся по правилам (которые следуют из свойств и определения последовательности чисел Люка):
Для значений, введённых по умолчанию, то есть получаем результат:
Делаем проверку этого значения. Для этого считаем НОД НОД и .
Если мы в первом шаге неудачно выбрали числа , то есть получилось так, что НОД, то тогда нужно переходить ко второму шагу. Иначе — работа завершена[1].
Пусть число имеет некоторый простой делитель, больший чем , но меньший некоторого , то есть:
Вводим последовательность простых чисел .
Вводим ещё одну последовательность:
Далее определяем:
Используя свойство , получаем первые элементы:
Далее используем свойство и получаем:
Таким образом, мы вычисляем
Далее считаем:
Как только получаем , то прекращаем вычисления[1].
Для значений, введённых по умолчанию, то есть получаем результат:
что является верным ответом.
Автором данного метода были проведены тесты и методов на машине AMDAHL 470-V7 на 497 различных числах, которые показали, что в среднем первый шаг алгоритма работает примерно в 2 раза медленнее первого шага алгоритма , а второй шаг — примерно в 4 раза медленнее[1].
В связи с тем, что -метод факторизации работает быстрее, -метод применяется на практике очень редко[1].
На данный момент (14.12.2013) три самых больших простых делителя[3], найденных методом , состоят из 60, 55 и 53 десятичных цифр.
| Кол-во цифр | p | Делитель числа | Найден (кем) | Найден (когда) | B | B2 |
|---|---|---|---|---|---|---|
| 60 | 725516237739635905037132916171116034279215026146021770250523 | A. Kruppa
P. Montgomery |
31.10.2007 | 10^11 | 10^15 | |
| 55 | 1273305908528677655311178780176836847652381142062038547 | 782*6^782 | P. Leyland | 16.05.2011 | 10^9 | 10^13 |
| 53 | 60120920503954047277077441080303862302926649855338567 | 682*5^682 | P. Leyland | 26.02.2011 | 10^8 | 10^12 |
Здесь — 2366-й член последовательности чисел Люка.
P+1 метод Уильямса.
