Русская Википедия:P+1-метод Уильямса

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Пусть <math>P</math> и <math>Q</math> — некоторые фиксированные целые числа. Последовательности чисел Люка определяются какШаблон:Sfn:

<math>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>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>\Delta = P^2 - 4Q.</math>

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

<math> \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> \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> \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> \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> \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>U_n(P,Q) = \frac{\alpha^n - \beta^n}{\alpha - \beta} </math>

и

<math>V_n(P,Q) = \alpha^n + \beta^n,</math>

где <math>\alpha</math> и <math>\beta</math> — корни характеристического многочлена

<math>x^2 - P\cdot x + Q</math>

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

<math>P = \alpha + \beta; \quad Q = \alpha \cdot \beta,</math>

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

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

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

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

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

Если p — нечётное простое число, <math>p \mid Q</math> и символ Лежандра <math>\epsilon = (\Delta/p)</math>, то:
<math> \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>

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

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

Файл:Первый шаг алгоритма.jpg
Графическое представление первого шага

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

<math>p+1=\prod^k_{i=1}q_i^{\alpha_i}, </math>

где <math>q_i</math> — простые числа.

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

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

Тогда <math>p+1 | R.</math>Шаблон:Sfn

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

И, следовательно, <math>p | </math> НОД <math>(U_R(P, Q), N),</math> то есть найден делитель искомого числа <math>N</math>Шаблон:Sfn.

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

Таким образом, мы без потери общности можем утверждать, что <math>Q=1.</math>Шаблон:Sfn

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

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

И, следовательно, <math>p | (V_R(P, 1) - 2).</math>Шаблон:Sfn

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

Обозначаем:

<math>V_n(P)=V_n(P,1), \quad U_n(P) = U_n(P, 1).</math>

Окончательно, нужно найти НОД<math>(V_R(P)-2, N).</math>Шаблон:Sfn

Для поиска <math>V_R(P)</math> поступаем следующим образомШаблон:Sfn:

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

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

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

<math>(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>V_0(P)=2, V_1(P)=P</math>

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

<math>\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>N=451889, R=2520, P=6</math> получаем результат:

374468

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

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

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

Файл:Второй шаг алгоритма.jpg
Графическое представление второго шага

Пусть число <math>p+1</math> имеет некоторый простой делитель<math>s</math>, больший чем <math>B</math>, но меньший некоторого <math>B_2</math>, то есть:

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

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

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

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

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

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

<math>\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>(4)</math> и получаем:

<math>\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>T[s_i], \forall i=1,2, \ldots, k</math>

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

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

Как только получаем <math>H_t \neq 1 </math>, то прекращаем вычисленияШаблон:Sfn.

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

139,

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

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

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

Применение

В связи с тем, что <math>p-1</math>-метод факторизации работает быстрее, <math>p+1</math>-метод применяется на практике очень редкоШаблон:Sfn.

Рекорды

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

Кол-во цифр p Делитель числа Найден (кем) Найден (когда) B B2
60 725516237739635905037132916171116034279215026146021770250523 <math>L_{2366}</math> A. Kruppa

P. Montgomery

31.10.2007 <math>10^{11}</math> <math>10^{15}</math>
55 1273305908528677655311178780176836847652381142062038547 <math>782\cdot6^{782}+1</math> P. Leyland 16.05.2011 <math>10^{9}</math> <math>10^{13}</math>
53 60120920503954047277077441080303862302926649855338567 <math>682\cdot5^{682}-1</math> P. Leyland 26.02.2011 <math>10^{8}</math> <math>10^{12}</math>

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

Примечания

Шаблон:Примечания

Литература

Ссылки