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

Меню
Главная
Случайная статья
Настройки

p+1-метод Уильямса
Материал из https://ru.wikipedia.org

$p+1$ -метод Уильямса — метод факторизации чисел

N\in \mathbb {N}

с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель

p

числа

n

. Аналогичен

p-1

-методу Полларда, но использует разложение на множители числа

p+1

. Имеет хорошие показатели скорости подсчёта только в случае, когда

p+1

легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев^[1].

Содержание

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

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

Пусть

P

Q

— некоторые фиксированные целые числа. Последовательности чисел Люка определяются как^[1]:

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}\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)

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

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

Пусть

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.

^[1]

Далее, согласно теореме

(T1),

если НОД

(N,Q)=1,(\Delta /p)=-1,

то

p|U_{R}(P,Q).

И, следовательно,

p|

НОД

(U_{R}(P,Q),N),

то есть найден делитель искомого числа

N

^[1].

Стоит обратить внимание, что числа

P,Q,p

не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как

p|U_{R}(P,Q),

то по свойству (2)

p|U_{2R}(P,Q).

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

p|U_{R}(P^{\prime },1).

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

Q=1.

^[1]

Далее пользуемся теоремой

(T1),

из которой делаем вывод, что

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

И, следовательно,

p|(V_{R}(P,1)-2).

^[1]

Теперь выбираем некоторое число

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).

^[1]

Для поиска

V_{R}(P)

поступаем следующим образом^[1]:

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

, то тогда нужно переходить ко второму шагу. Иначе — работа завершена^[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

, то прекращаем вычисления^[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 раза медленнее^[1].

Применение

В связи с тем, что

p-1

-метод факторизации работает быстрее,

p+1

-метод применяется на практике очень редко^[1].

Рекорды

На данный момент (01.01.2025) три самых больших простых делителя^[3], найденных методом

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, 1982.
Lehmer, 1930.
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