p+1-метод Уильямса

-метод Уильямса — метод факторизации чисел с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель числа . Аналогичен -методу Полларда, но использует разложение на множители числа . Имеет хорошие показатели производительности только в случае, когда легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев[1].

Последовательности чисел Люка

Для дальнейших выкладок нам понадобится ввести последовательности чисел Люка и перечислить некоторые их свойства.

Пусть и  — некоторые фиксированные целые числа. Последовательности чисел Люка определяются как[1]:

Пусть также

Последовательности имеют следующие свойства:

Для доказательства данных свойств рассмотрим явные формулы последовательности чисел Люка:

и

где и  — корни характеристического многочлена

Используя явные формулы и теорему Виетта:

получаем выражения и

Далее выделяем ещё одно свойство:

Если НОД и то: и откуда

И, наконец, формулируем теорему:

Если p — нечётное простое число, и символ Лежандра , то:

Доказательство данной теоремы трудоёмкое, и его можно найти в книге Д. Г. Лемера[2].

Первый шаг алгоритма

Графическое представление первого шага

Пусть  — простой делитель факторизуемого числа , и выполнено разложение:

где  — простые числа.

Пусть

Введём число где степени выбираются таким образом, что

Тогда [1]

Далее, согласно теореме если НОД то

И, следовательно, НОД то есть найден делитель искомого числа [1].

Стоит обратить внимание, что числа не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как то по свойству (2) Далее воспользуемся свойством (6) и получим:

Таким образом, мы без потери общности можем утверждать, что [1]

Далее пользуемся теоремой из которой делаем вывод, что

И, следовательно, [1]

Теперь выбираем некоторое число такое, что НОД

Обозначаем:

Окончательно, нужно найти НОД[1]

Для поиска поступаем следующим образом[1]:

1) раскладываем в двоичный вид: где .

2) вводим последовательность натуральных чисел . При этом ;

3) ищем пары значений по следующему правилу:

при этом

4) значения ищутся по правилам (которые следуют из свойств и определения последовательности чисел Люка):

.

Для значений, введённых по умолчанию, то есть получаем результат:

374468

Делаем проверку этого значения. Для этого считаем НОД НОД и .

Если мы в первом шаге неудачно выбрали числа , то есть получилось так, что НОД, то тогда нужно переходить ко второму шагу. Иначе — работа завершена[1].

Второй шаг алгоритма

Графическое представление второго шага

Пусть число имеет некоторый простой делитель, больший чем , но меньший некоторого , то есть:

, где

Вводим последовательность простых чисел .

Вводим ещё одну последовательность:

Далее определяем:

.

Используя свойство , получаем первые элементы:

.

Далее используем свойство и получаем:

.

Таким образом, мы вычисляем

Далее считаем:

НОД для

Как только получаем , то прекращаем вычисления[1].

Для значений, введённых по умолчанию, то есть получаем результат:

139,

что является верным ответом.

Сравнение скорости работы

Автором данного метода были проведены тесты и методов на машине 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
55 1273305908528677655311178780176836847652381142062038547 P. Leyland 16.05.2011
53 60120920503954047277077441080303862302926649855338567 P. Leyland 26.02.2011

Здесь  — 2366-й член последовательности чисел Люка.

Примечания

Литература

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.