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].

Рекорды

На данный момент (27.09.2023) три самых больших простых делителя[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-й член последовательности чисел Люка.

Примечания

  1. 1 2 3 4 5 6 7 8 9 10 11 12 Williams, 1982.
  2. Lehmer, 1930.
  3. Record Factors Found By The p+1 Method. Дата обращения: 13 декабря 2013. Архивировано 18 декабря 2013 года.

Литература

  • Williams H. C. A p+1 method of factoring (англ.) = A p+1 method of factoring // American Mathematical Society. — 1982. — Т. 39, вып. 159. — С. 225—234. — ISSN 00255718.
  • D. H. Lehmer. An extended theory of Lucas' functions (англ.) = An extended theory of Lucas' functions // Ann. of Math.. — 1930. — Т. 31, вып. 2. — С. 419—448.
  • Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. — Казань: Казанский Университет, 2011. — С. 60—61. — 190 с.

Ссылки