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

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

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


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

U0(P,Q)=0,U1(P,Q)=1,Un+2(P,Q)=PUn+1(P,Q)QUn(P,Q),n0U0(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),n0V0(P,Q)=2,V1(P,Q)=P,Vn+2(P,Q)=PVn+1(P,Q)QVn(P,Q),n0
 Пусть также Δ=P24Q.Δ=P24Q.
 Последовательности имеют следующие свойства:

{U2n=VnUn,V2n=V2n2Q2n(1){U2n=VnUn,V2n=V2n2Q2n(1)


{U2n1=U2nQU2n1,V2n1=VnVn1PQn1(2){U2n1=U2nQU2n1,V2n1=VnVn1PQn1(2)


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


{Un+m=UmUn+1QUm1Un,ΔUn+m=VmVn+1QVm1Vn(4){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(Vk(P,Q),Qk)=Unk(P,Q)/Uk(P,Q),Vn(Vk(P,Q),Qk)=Vnk(P,Q)(5)
 Для доказательства данных свойств рассмотрим явные формулыпоследовательности чисел Люка:

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

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

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

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

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

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

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


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

p+1=ki=1qαii,
 где qi — простые числа.
 Пусть B=max{qαii|i:1ik}.
 Введём число R=ki=1qβii, где степени βiвыбираются таким образом, чтоqβiiB,qβi+1i>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=ti=0bi2ti, где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;V2fV2f2modN;V2f+1PV2fVfVf1PmodN.
 Для значений, введённых по умолчанию, то есть 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(ki=1qαii)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= НОД(ti=1T[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-й член последовательности чисел Люка.