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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

(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^2_n - 2Q^2_n \end{matrix} \right. \quad(1)


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


 \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^k_{i=1}q_i^{\alpha_i},

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

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

Введём число R=\prod^k_{i=1}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^t_{i=0}b_i2^{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_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..

Для значений, введённых по умолчанию, т.е. 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^k_{i=1}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_iR}(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^t_{i=1}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].

Рекорды[править | править вики-текст]

На данный момент (14.12.2013) три самых больших простых делителя[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*6^782 P. Leyland 16.05.2011 10^9 10^13
53 60120920503954047277077441080303862302926649855338567 682*5^682 P. Leyland 26.02.2011 10^8 10^12

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]