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

($P+1$) — метод Уильямса — метод факторизации чисел $n$ ∈ N с помощью последовательностей чисел Люка, разработанный в 1982 году. Алгоритм находит простой делитель $p$ числа $n$. Аналогичен ($P-1$) — методу Полларда, но использует разложение на множители числа $p+1$. Имеет хорошие показатели производительности только в случае, когда $p+1$ легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев.

Суть алгоритма

Рассматривается последовательность чисел Люка:

$~u_0 = 0, u_1= u, u_{n+1} = \Phi u_n - \Theta u_{n-1}$,

где $~\Phi$ и $~\Theta$ — фиксированные целые числа.

$~p$ — простой делитель числа $~n$, причем $~p+1$ является $~B$-степенно гладким, то есть

$p = \prod_{i=1}^k q_i^{\alpha_i} - 1$

где $~q_i$ — простые числа, $q_i^{\alpha_i} \leq B$.

Пусть ∃ последовательность чисел $\beta_i \isin N$, такая, что каждый её член удовлетворяет условиям

$q_i^{\beta_i} \le B,$ $q_i^{\beta_i+1} > B, i = 1, \ldots ,k$.

Пусть $R = \prod_{i=1}^k q_i^{\beta_i}$, тогда $~p+1 | R$. Далее, если для последовательности чисел Люка $~\Theta$ взаимно прост с $~n$ и выполняется условие

$\left( {\Phi^2 - 4\Theta\over p}\right) = -1$, то по свойствам последовательности чисел Люка

$~p |$ НОД$\left({u_r,n}\right)$

Далее алгоритм вычисляет элемент последовательности $~u_r$ и находит НОД$\left({u_r,n}\right)$.

Литература

1. Williams H. C. A p +1 method of factoring Math. Comp. 1982.V. 39 (159). P. 225—234.
2. Bach E., Shallit J. Factoring with cyclotomic polynomials Math.Comp. 1989. V. 52 (185). P. 201—219.

См. также

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

Ссылки

• http://pagesperso-orange.fr/colin.barker/lpa/big_pp1.htm