-метод Уильямса — метод факторизации чисел с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель числа . Аналогичен -методу Полларда, но использует разложение на множители числа . Имеет хорошие показатели скорости подсчёта только в случае, когда легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев.
Последовательности чисел Люка
Для дальнейших выкладок нам понадобится ввести последовательности чисел Люка и перечислить некоторые их свойства.
Пусть и — некоторые фиксированные целые числа. Последовательности чисел Люка определяются как:
Пусть также
Последовательности имеют следующие свойства:
Для доказательства данных свойств рассмотрим формулы последовательности чисел Люка:
и
где и — корни характеристического многочлена
Используя явные формулы и теорему Виетта:
получаем выражения и
Далее выделяем ещё одно свойство:
Если НОД и то: и откуда
И затем формулируем теорему: Если p — нечётное простое число, и символ Лежандра , то:
Доказательство данной теоремы трудоёмкое, и его можно найти в книге Д. Г. Лемера.
Первый шаг алгоритма
Пусть — простой делитель факторизуемого числа , и выполнено разложение:
где — простые числа.
Пусть
Введём число где степени выбираются таким образом, что
Тогда
Далее, согласно теореме если НОД то
И, следовательно, НОД то есть найден делитель искомого числа .
Стоит обратить внимание, что числа не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как то по свойству (2) Далее воспользуемся свойством (6) и получим:
Таким образом, мы без потери общности можем утверждать, что
Далее пользуемся теоремой из которой делаем вывод, что
И, следовательно,
Теперь выбираем некоторое число такое, что НОД
Обозначаем:
Окончательно, нужно найти НОД
Для поиска поступаем следующим образом:
1) раскладываем в двоичный вид: где .
2) вводим последовательность натуральных чисел . При этом ;
3) ищем пары значений по следующему правилу:
при этом
4) значения ищутся по правилам (которые следуют из свойств и определения последовательности чисел Люка): .
Для значений, введённых по умолчанию, то есть получаем результат: 374468 Делаем проверку этого значения. Для этого считаем НОД НОД и .
Если мы в первом шаге неудачно выбрали числа , то есть получилось так, что НОД, то тогда нужно переходить ко второму шагу. Иначе — работа завершена.
Второй шаг алгоритма
Пусть число имеет некоторый простой делитель, больший чем , но меньший некоторого , то есть: , где Вводим последовательность простых чисел .
Вводим ещё одну последовательность:
Далее определяем: .
Используя свойство , получаем первые элементы: .
Далее используем свойство и получаем: .
Таким образом, мы вычисляем
Далее считаем: НОД для
Как только получаем , то прекращаем вычисления.
Для значений, введённых по умолчанию, то есть получаем результат: 139, что является верным ответом.
Сравнение скорости работы Автором данного метода были проведены тесты и методов на машине AMDAHL 470-V7 на 497 различных числах, которые показали, что в среднем первый шаг алгоритма работает примерно в 2 раза медленнее первого шага алгоритма , а второй шаг — примерно в 4 раза медленнее.
Применение В связи с тем, что -метод факторизации работает быстрее, -метод применяется на практике очень редко.
Рекорды На данный момент (01.01.2025) три самых больших простых делителя, найденных методом , состоят из 60, 55 и 53 десятичных цифр. Кол-во цифр p Делитель числа Найден (кем) Найден (когда) B B2 60 725516237739635905037132916171116034279215026146021770250523 A. Kruppa P. Montgomery 31.10.2007 55 1273305908528677655311178780176836847652381142062038547 P. Leyland 16.05.2011 53 60120920503954047277077441080303862302926649855338567 P. Leyland 26.02.2011 Здесь — 2366-й член последовательности чисел Люка.
Примечания
Литература
Ссылки https://web.archive.org/web/20170222131210/http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method
Категория:Алгоритмы факторизации