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

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

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

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

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

[math]\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 }[/math]

[math]\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 }[/math]

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

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

[math]\displaystyle{ \left\{ \begin{matrix} U_{2n} = V_n \cdot U_n, \\ V_{2n} = V^2_n - 2Q^2_n \end{matrix} \right. \quad(1) }[/math]

[math]\displaystyle{ \left\{ \begin{matrix} U_{2n-1} = U^2_n - Q \cdot U^2_{n-1}, \\ V_{2n-1} = V_n \cdot V_{n-1} - P \cdot Q^{n-1}\end{matrix} \right. \quad(2) }[/math]

[math]\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) }[/math]

[math]\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) }[/math]

[math]\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) }[/math]

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

[math]\displaystyle{ U_n(P,Q) = \frac{\alpha^n - \beta^n}{\alpha - \beta} }[/math]

и

[math]\displaystyle{ V_n(P,Q) = \alpha^n + \beta^n, }[/math]

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

[math]\displaystyle{ x^2 - P\cdot x + Q }[/math]

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

[math]\displaystyle{ P = \alpha + \beta; \quad Q = \alpha \cdot \beta, }[/math]

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

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

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

[math]\displaystyle{ U_{2m}(P,Q)\equiv P \cdot Q^{m-1}\cdot U_m(P^\prime, 1) \mod N \quad (6) }[/math]

И, наконец, формулируем теорему:

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

[math]\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) }[/math]

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

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

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

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

[math]\displaystyle{ p+1=\prod^k_{i=1}q_i^{\alpha_i}, }[/math]

где [math]\displaystyle{ q_i }[/math] — простые числа.

Пусть [math]\displaystyle{ B = \max \{q_i^{\alpha_i} | \forall i: 1 \leq i \leq k\}. }[/math]

Введём число [math]\displaystyle{ R=\prod^k_{i=1}q_i^{\beta_i}, }[/math] где степени [math]\displaystyle{ \beta_i }[/math] выбираются таким образом, что [math]\displaystyle{ q_i^{\beta_i}\leq B, q_i^{\beta_i + 1} \gt B \quad \forall i: 1 \leq i \leq k. }[/math]

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

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

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

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

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

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

[math]\displaystyle{ V_{(p-\epsilon )m}(P,1) \equiv 2 \mod p; }[/math]

И, следовательно, [math]\displaystyle{ p | (V_R(P, 1) - 2). }[/math]

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

Обозначаем:

[math]\displaystyle{ V_n(P)=V_n(P,1), \quad U_n(P) = U_n(P, 1). }[/math]

Окончательно, нужно найти НОД[math]\displaystyle{ (V_R(P)-2, N). }[/math]

Для поиска [math]\displaystyle{ V_R(P) }[/math] поступаем следующим образом:

1) раскладываем [math]\displaystyle{ R }[/math] в двоичный вид: [math]\displaystyle{ R=\sum^t_{i=0}b_i2^{t-i}, }[/math] где [math]\displaystyle{ b_i=0,1 }[/math].

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

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

[math]\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. }[/math]

при этом [math]\displaystyle{ V_0(P)=2, V_1(P)=P }[/math]

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

[math]\displaystyle{ \left\{ \begin{matrix} V_{2f-1} \equiv V_fV{f-1}-P \mod N; \\ V_{2f} \equiv V_f^2-2 \mod N; \\ V_{2f+1} \equiv PV_f^2-V_fV_{f-1}-P \mod N \end{matrix} \right. }[/math].

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

374468

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

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

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

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

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

[math]\displaystyle{ p=s \cdot (\prod^k_{i=1}q_i^{\alpha_i})-1 }[/math], где [math]\displaystyle{ B \lt s \leq B_2 }[/math]

Вводим последовательность простых чисел [math]\displaystyle{ \{s_j: B \lt s_j \leq B_2 \quad \forall j = 1, 2, ..., k \} }[/math].

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

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

[math]\displaystyle{ T[s_i] \equiv \Delta U_{s_iR}(P)/U_R(P) \mod N }[/math].

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

[math]\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. }[/math].

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

[math]\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. }[/math].

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

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

[math]\displaystyle{ H_t = }[/math] НОД[math]\displaystyle{ (\prod^t_{i=1}T[s_i], N) }[/math] для [math]\displaystyle{ t=1,2, \ldots, k }[/math]

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

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

139,

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

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

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

Применение

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

Рекорды

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

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

Здесь [math]\displaystyle{ L_{2366} }[/math] — 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