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

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

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

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

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

$U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q)-Q\cdot U_{n}(P,Q),n\geq 0$

$V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q)-Q\cdot V_{n}(P,Q),n\geq 0$

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

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

$\left\{{\begin{matrix}U_{2n}=V_{n}\cdot U_{n},\\V_{2n}=V_{n}^{2}-2Q_{n}^{2}\end{matrix}}\right.\quad (1)$

$\left\{{\begin{matrix}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{matrix}}\right.\quad (2)$

$\left\{{\begin{matrix}\Delta U_{n}=P\cdot V_{n}-2Q\cdot V_{n-1},\\V_{n}=P\cdot U_{n}-2Q\cdot U_{n-1}\end{matrix}}\right.\quad (3)$

$\left\{{\begin{matrix}U_{n+m}=U_{m}\cdot U_{n+1}-Q\cdot U_{m-1}\cdot U_{n},\\\Delta U_{n+m}=V_{m}\cdot V_{n+1}-Q\cdot V_{m-1}\cdot V_{n}\end{matrix}}\right.\quad (4)$

$\left\{{\begin{matrix}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{matrix}}\right.\quad (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 ;\quad Q=\alpha \cdot \beta ,$

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

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

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

$U_{2m}(P,Q)\equiv P\cdot Q^{m-1}\cdot U_{m}(P^{\prime },1)\mod N\quad (6)$

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

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

$\left\{{\begin{matrix}U_{(p-\epsilon )m}(P,Q)\equiv 0\mod p,\\V_{(p-\epsilon )m}(P,Q)\equiv 2Q^{m(1-\epsilon )/2}\mod p\end{matrix}}\right.\quad (T1)$

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

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

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

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

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

где $q_{i}$ — простые числа.

Пусть $B=\max\{q_{i}^{\alpha _{i}}|\forall i:1\leq i\leq k\}.$

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

Тогда $p+1|R.$

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

И, следовательно, $p|$ НОД $(U_{R}(P,Q),N),$ то есть найден делитель искомого числа $N$.

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

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

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

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

И, следовательно, $p|(V_{R}(P,1)-2).$

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

Обозначаем:

$V_{n}(P)=V_{n}(P,1),\quad U_{n}(P)=U_{n}(P,1).$

Окончательно, нужно найти НОД$(V_{R}(P)-2,N).$

Для поиска $V_{R}(P)$ поступаем следующим образом:

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})=\left\{{\begin{matrix}(V_{2f_{k}},V_{2f_{k}-1}),when\quad b_{k+1}=0;\\(V_{2f_{k}+1},V_{2f_{k}}),when\quad b_{k+1}=1\end{matrix}}\right.$

при этом $V_{0}(P)=2,V_{1}(P)=P$

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

$\left\{{\begin{matrix}V_{2f-1}\equiv V_{f}V{f-1}-P\mod N;\\V_{2f}\equiv V_{f}^{2}-2\mod N;\\V_{2f+1}\equiv PV_{f}^{2}-V_{f}V_{f-1}-P\mod N\end{matrix}}\right.$.

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

374468

Делаем проверку этого значения. Для этого считаем НОД$(V_{R}(P)-2,N)=$ НОД$(374468-2,451889)=139$ и $\quad 451889\vdots 139$.

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

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

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

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

$p=s\cdot (\prod _{i=1}^{k}q_{i}^{\alpha _{i}})-1$, где $B<s\leq B_{2}$

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

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

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

$T[s_{i}]\equiv \Delta U_{s_{i}R}(P)/U_{R}(P)\mod N$.

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

$\left\{{\begin{matrix}T[s_{1}]\equiv PV[s_{1}]-2V[s_{1}-1]\mod N;\\T[s_{1}-1]\equiv 2V[s_{1}]-PV[s_{1}-1]\mod N\end{matrix}}\right.$.

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

$\left\{{\begin{matrix}T[s_{i+1}]\equiv T[s_{i}]U[2d_{i}+1]-T[s_{i}-1]U[2d_{i}]\mod N,\\T[s_{i+1}-1]\equiv T[s_{i}]U[2d_{i}]-T[s_{i}-1]U[2d_{i}-1]\mod N\end{matrix}}\right.$.

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

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

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

Как только получаем $H_{t}\neq 1$, то прекращаем вычисления.

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

139,

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

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

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

Применение

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

Рекорды

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

Литература

• 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 с.

Ссылки

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