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

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

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


 Для дальнейших выкладок нам понадобится ввести последовательности чисел Люка и перечислить некоторые их свойства.
 Пусть P и Q — некоторые фиксированные целые числа. Последовательности чисел Люка определяются как:

U0(P,Q)=0,U1(P,Q)=1,Un+2(P,Q)=PUn+1(P,Q)QUn(P,Q),n0
V0(P,Q)=2,V1(P,Q)=P,Vn+2(P,Q)=PVn+1(P,Q)QVn(P,Q),n0
  Пусть также Δ=P24Q.
 Последовательности имеют следующие свойства:

{U2n=VnUn,V2n=Vn22Qn2(1)


{U2n1=Un2QUn12,V2n1=VnVn1PQn1(2)


{ΔUn=PVn2QVn1,Vn=PUn2QUn1(3)


{Un+m=UmUn+1QUm1Un,ΔUn+m=VmVn+1QVm1Vn(4)


{Un(Vk(P,Q),Qk)=Unk(P,Q)/Uk(P,Q),Vn(Vk(P,Q),Qk)=Vnk(P,Q)(5)
  Для доказательства данных свойств рассмотрим явные формулы последовательности чисел Люка:

Un(P,Q)=αnβnαβ
  и

Vn(P,Q)=αn+βn,
  где α и β — корни характеристического многочлена

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

P=α+β;Q=αβ,
  получаем выражения (1),(2),(3),(4) и (5).
 Далее выделяем ещё одно свойство:
 Если НОД(N,Q)=1 и PQP22QmodN, то: Pα/β+β/α и Q1, откуда

U2m(P,Q)PQm1Um(P,1)modN(6)
  И, наконец, формулируем теорему:

  Если p — нечётное простое число, pQ и символ Лежандра ϵ=(Δ/p), то:
{U(pϵ)m(P,Q)0modp,V(pϵ)m(P,Q)2Qm(1ϵ)/2modp(T1)
  Доказательство данной теоремы трудоёмкое, и его можно найти в книге Д. Г. Лемера.

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


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

p+1=i=1kqiαi,
  где qi — простые числа.
 Пусть B=max{qiαi|i:1ik}.
 Введём число R=i=1kqiβi, где степени βi выбираются таким образом, что qiβiB,qiβi+1>Bi:1ik.
 Тогда p+1|R.
 Далее, согласно теореме (T1), если НОД(N,Q)=1,(Δ/p)=1, то p|UR(P,Q).
 И, следовательно, p| НОД (UR(P,Q),N), то есть найден делитель искомого числа N.
 Стоит обратить внимание, что числа P,Q,p не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как p|UR(P,Q), то по свойству (2) p|U2R(P,Q). Далее воспользуемся свойством (6) и получим: p|UR(P,1).
 Таким образом, мы без потери общности можем утверждать, что Q=1.
 Далее пользуемся теоремой (T1), из которой делаем вывод, что

V(pϵ)m(P,1)2modp;
  И, следовательно, p|(VR(P,1)2).
 Теперь выбираем некоторое число P такое, что НОД (P24,N)=1;
 Обозначаем:

Vn(P)=Vn(P,1),Un(P)=Un(P,1).
  Окончательно, нужно найти НОД(VR(P)2,N).
 Для поиска VR(P) поступаем следующим образом:
 1) раскладываем R в двоичный вид: R=i=0tbi2ti, где bi=0,1.
 2) вводим последовательность натуральных чисел {fn}:f0=1;fk+1=2fk+bk+1. При этом ft=R;
 3) ищем пары значений (Vfk+1,Vfk+11) по следующему правилу:

(Vfk+1,Vfk+11)={(V2fk,V2fk1),whenbk+1=0;(V2fk+1,V2fk),whenbk+1=1
 при этом V0(P)=2,V1(P)=P
  4) значения V2fk1,V2fk,V2fk+1 ищутся по правилам (которые следуют из свойств (1),(2) и определения последовательности чисел Люка):

{V2f1VfVf1PmodN;V2fVf22modN;V2f+1PVf2VfVf1PmodN.
  Для значений, введённых по умолчанию, то есть N=451889,R=2520,P=6 получаем результат:

  374468
  Делаем проверку этого значения. Для этого считаем НОД(VR(P)2,N)= НОД(3744682,451889)=139 и 451889139.
 Если мы в первом шаге неудачно выбрали числа R,P, то есть получилось так, что НОД(VR(P)2,N)=1, то тогда нужно переходить ко второму шагу. Иначе — работа завершена.

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


 Пусть число p+1 имеет некоторый простой делительs, больший чем B, но меньший некоторого B2, то есть:

p=s(i=1kqiαi)1, где B<sB2
  Вводим последовательность простых чисел {sj:B<sjB2j=1,2,...,k}.
 Вводим ещё одну последовательность: {dj:2dj=sj+1sjj=1,2,...,k1}
 Далее определяем:

T[si]ΔUsiR(P)/UR(P)modN.
  Используя свойство (5), получаем первые элементы:

{T[s1]PV[s1]2V[s11]modN;T[s11]2V[s1]PV[s11]modN.
  Далее используем свойство (4) и получаем:

{T[si+1]T[si]U[2di+1]T[si1]U[2di]modN,T[si+11]T[si]U[2di]T[si1]U[2di1]modN.
  Таким образом, мы вычисляем T[si],i=1,2,,k
 Далее считаем:

Ht= НОД(i=1tT[si],N) для t=1,2,,k
  Как только получаем Ht1, то прекращаем вычисления.
 Для значений, введённых по умолчанию, то есть N=451889,B=10,B2=50,P=7 получаем результат:

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

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


 Автором данного метода были проведены тесты p1 и p+1 методов на машине AMDAHL 470-V7 на 497 различных числах, которые показали, что в среднем первый шаг алгоритма p+1 работает примерно в 2 раза медленнее первого шага алгоритма p1, а второй шаг — примерно в 4 раза медленнее.

Применение


 В связи с тем, что p1-метод факторизации работает быстрее, p+1-метод применяется на практике очень редко.

Рекорды


 На данный момент (14.12.2013) три самых больших простых делителя, найденных методом P+1, состоят из 60, 55 и 53 десятичных цифр.
Кол-во цифрpДелитель числаНайден (кем)Найден (когда)BB2
60725516237739635905037132916171116034279215026146021770250523L2366A. Kruppa P. Montgomery31.10.200710111015
5512733059085286776553111787801768368476523811420620385477826782+1P. Leyland16.05.20111091013
536012092050395404727707744108030386230292664985533856768256821P. Leyland26.02.20111081012

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