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

Шаблон:Заголовок с маленькой буквы $p+1$-метод Уильямса — метод факторизации чисел $N\in \mathbb{N}$ с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель $p$ числа $n$. Аналогичен $p-1$-методу Полларда, но использует разложение на множители числа $p+1$. Имеет хорошие показатели скорости подсчёта только в случае, когда $p+1$ легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаевШаблон:Sfn.

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

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

Пусть $P$ и $Q$ — некоторые фиксированные целые числа. Последовательности чисел Люка определяются какШаблон:Sfn:

$U_0(P,Q)=0,U_1(P,Q)=1,U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q)-Q\cdot U_n(P,Q),n\ge 0$

$V_0(P,Q)=2,V_1(P,Q)=P,V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q)-Q\cdot V_n(P,Q),n\ge 0$

Пусть также $\mathrm{\Delta }=P^2-4Q.$

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

$\{\begin{array}{c}{U}_{2n}=V_n\cdot U_n,\\ V_{2n}=V_n^2-2Q^n\end{array}(1)$

$\{\begin{array}{c}{U}_{2n-1}=U_n^2-Q\cdot U_{n-1}^2,\\ V_{2n-1}=V_n\cdot V_{n-1}-P\cdot Q^{n-1}\end{array}(2)$

$\{\begin{array}{c}\mathrm{\Delta }{U}_n=P\cdot V_n-2Q\cdot V_{n-1},\\ V_n=P\cdot U_n-2Q\cdot U_{n-1}\end{array}(3)$

$\{\begin{array}{c}{U}_{n+m}=U_m\cdot U_{n+1}-Q\cdot U_{m-1}\cdot U_n,\\ \mathrm{\Delta }{U}_{n+m}=V_m\cdot V_{n+1}-Q\cdot V_{m-1}\cdot V_n\end{array}(4)$

$\{\begin{array}{c}{U}_n(V_k(P,Q),Q^k)=U_{nk}(P,Q)/U_k(P,Q),\\ V_n(V_k(P,Q),Q^k)=V_{nk}(P,Q)\end{array}(5)$

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

$U_n(P,Q)=\frac{{\alpha }^n-{\beta }^n}{\alpha -\beta }$

и

$V_n(P,Q)={\alpha }^n+{\beta }^n,$

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

$x^2-P\cdot x+Q$

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

$P=\alpha +\beta ;Q=\alpha \cdot \beta ,$

получаем выражения $(1),(2),(3),(4)$ и $(5).$

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

Если НОД$(N,Q)=1$ и $P^{\prime }Q\equiv P^2-2QmodN,$ то: $P^{\prime }\equiv \alpha /\beta +\beta /\alpha$ и $Q^{\prime }\equiv 1,$ откуда

$U_{2m}(P,Q)\equiv P\cdot Q^{m-1}\cdot U_m(P^{\prime },1)modN(6)$

И затем формулируем теорему:

Если p — нечётное простое число, $p\mid Q$ и символ Лежандра $ϵ=(\mathrm{\Delta }/p)$, то:

$\{\begin{array}{c}{U}_{(p-ϵ)m}(P,Q)\equiv 0modp,\\ V_{(p-ϵ)m}(P,Q)\equiv 2Q^{m(1-ϵ)/2}modp\end{array}(T1)$

Доказательство данной теоремы трудоёмкое, и его можно найти в книге Д. Г. ЛемераШаблон:Sfn.

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

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

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

$p+1=\prod _{i=1}^k{q}_i^{{\alpha }_i},$

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

Пусть $B=max\{q_i^{{\alpha }_i}|\mathrm{\forall }i:1\le i\le k\}.$

Введём число $R=\prod _{i=1}^k{q}_i^{{\beta }_i},$ где степени ${\beta }_i$ выбираются таким образом, что $q_i^{{\beta }_i}\le B,q_i^{{\beta }_i+1}>B\mathrm{\forall }i:1\le i\le k.$

Тогда $p+1|R.$Шаблон:Sfn

Далее, согласно теореме $(T1),$ если НОД$(N,Q)=1,(\mathrm{\Delta }/p)=-1,$ то $p|U_R(P,Q).$

И, следовательно, $p|$ НОД $(U_R(P,Q),N),$ то есть найден делитель искомого числа $N$Шаблон:Sfn.

Стоит обратить внимание, что числа $P,Q,p$ не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как $p|U_R(P,Q),$ то по свойству (2) $p|U_{2R}(P,Q).$ Далее воспользуемся свойством (6) и получим: $p|U_R(P^{\prime },1).$

Таким образом, мы без потери общности можем утверждать, что $Q=1.$Шаблон:Sfn

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

$V_{(p-ϵ)m}(P,1)\equiv 2modp;$

И, следовательно, $p|(V_R(P,1)-2).$Шаблон:Sfn

Теперь выбираем некоторое число $P$ такое, что НОД $(P^2-4,N)=1;$

Обозначаем:

$V_n(P)=V_n(P,1),U_n(P)=U_n(P,1).$

Окончательно, нужно найти НОД$(V_R(P)-2,N).$Шаблон:Sfn

Для поиска $V_R(P)$ поступаем следующим образомШаблон:Sfn:

1) раскладываем $R$ в двоичный вид: $R=\sum _{i=0}^t{b}_i{2}^{t-i},$ где $b_i=0,1$.

2) вводим последовательность натуральных чисел $\{f_n\}:f_0=1;f_{k+1}=2f_k+b_{k+1}$. При этом $f_t=R$;

3) ищем пары значений $(V_{f_{k+1}},V_{f_{k+1}-1})$ по следующему правилу:

$(V_{f_{k+1}},V_{f_{k+1}-1})=\{\begin{array}{c}(V_{2f_k},V_{2f_k-1}),when{b}_{k+1}=0;\\ (V_{2f_k+1},V_{2f_k}),when{b}_{k+1}=1\end{array}$

при этом $V_0(P)=2,V_1(P)=P$

4) значения $V_{2f_k-1},V_{2f_k},V_{2f_k+1}$ ищутся по правилам (которые следуют из свойств $(1),(2)$ и определения последовательности чисел Люка):

$\{\begin{array}{c}{V}_{2f-1}\equiv V_f{V}_{f-1}-PmodN;\\ V_{2f}\equiv V_f^2-2modN;\\ V_{2f+1}\equiv P{V}_f^2-V_f{V}_{f-1}-PmodN\end{array}$.

Для значений, введённых по умолчанию, то есть $N=451889,R=2520,P=6$ получаем результат:

374468

Делаем проверку этого значения. Для этого считаем НОД$(V_R(P)-2,N)=$ НОД$(374468-2,451889)=139$ и $451889⋮139$.

Если мы в первом шаге неудачно выбрали числа $R,P$, то есть получилось так, что НОД$(V_R(P)-2,N)=1$, то тогда нужно переходить ко второму шагу. Иначе — работа завершенаШаблон:Sfn.

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

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

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

$p=s\cdot (\prod _{i=1}^k{q}_i^{{\alpha }_i})-1$, где $B<s\le B_2$

Вводим последовательность простых чисел $\{s_j:B<s_j\le B_2\mathrm{\forall }j=1,2,\mathrm{...},k\}$.

Вводим ещё одну последовательность: $\{d_j:2d_j=s_{j+1}-s_j\mathrm{\forall }j=1,2,\mathrm{...},k-1\}$

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

$T[s_i]\equiv \mathrm{\Delta }{U}_{s_{i}R}(P)/U_R(P)modN$.

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

$\{\begin{array}{c}T[s_1]\equiv PV[s_1]-2V[s_1-1]modN;\\ T[s_1-1]\equiv 2V[s_1]-PV[s_1-1]modN\end{array}$.

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

$\{\begin{array}{c}T[s_{i+1}]\equiv T[s_i]U[2d_i+1]-T[s_i-1]U[2d_i]modN,\\ T[s_{i+1}-1]\equiv T[s_i]U[2d_i]-T[s_i-1]U[2d_i-1]modN\end{array}$.

Таким образом, мы вычисляем $T[s_i],\mathrm{\forall }i=1,2,\dots ,k$

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

$H_t=$ НОД$(\prod _{i=1}^{t}T[s_i],N)$ для $t=1,2,\dots ,k$

Как только получаем $H_t\ne 1$, то прекращаем вычисленияШаблон:Sfn.

Для значений, введённых по умолчанию, то есть $N=451889,B=10,B_2=50,P=7$ получаем результат:

139,

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

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

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

Применение

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

Рекорды

На данный момент (01.01.2025) три самых больших простых делителя, найденных методом $P+1$, состоят из 60, 55 и 53 десятичных цифр.

Кол-во цифр	p	Делитель числа	Найден (кем)	Найден (когда)	B	B2
60	725516237739635905037132916171116034279215026146021770250523	$L_{2366}$	A. Kruppa P. Montgomery	31.10.2007	$10^{11}$	$10^{15}$
55	1273305908528677655311178780176836847652381142062038547	$782\cdot 6^{782}+1$	P. Leyland	16.05.2011	$10^9$	$10^{13}$
53	60120920503954047277077441080303862302926649855338567	$682\cdot 5^{682}-1$	P. Leyland	26.02.2011	$10^8$	$10^{12}$

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

Ссылки

• https://web.archive.org/web/20170222131210/http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method