Русская Википедия: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.
Первый шаг алгоритма
Пусть <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.
Второй шаг алгоритма
Пусть число <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-й член последовательности чисел Люка.
Примечания
Литература
Ссылки
