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

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

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

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

Пусть ${\displaystyle P}$ и ${\displaystyle Q}$ — некоторые фиксированные целые числа. Последовательности чисел Люка определяются как^[1]:

${\displaystyle 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}$

${\displaystyle 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}$

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

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

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

${\displaystyle \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)}$

${\displaystyle \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)}$

${\displaystyle \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)}$

${\displaystyle \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)}$

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

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

и

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

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

${\displaystyle x^{2}-P\cdot x+Q}$

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

${\displaystyle P=\alpha +\beta$ ;\quad Q=\alpha \cdot \beta ,}

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

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

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

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

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

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

${\displaystyle \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)}$

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

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

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

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

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

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

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

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

Тогда ${\displaystyle p+1|R.}$^[1]

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

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

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

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

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

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

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

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

Обозначаем:

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

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

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

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

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

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

${\displaystyle (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.}$

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

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

${\displaystyle \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.}$.

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

374468

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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.}$.

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

${\displaystyle \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.}$.

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

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

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

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

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

139,

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

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

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

Применение

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

Рекорды

На данный момент (27.09.2023) три самых больших простых делителя^[3], найденных методом ${\displaystyle P+1}$, состоят из 60, 55 и 53 десятичных цифр.

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

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

Примечания

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

Ссылки

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