алгоритм Вильямса p + 1

В теории вычислительных чисел, Wil Алгоритм liams p + 1 представляет собой алгоритм целочисленной факторизации, один из семейства алгоритмов факторизации алгебраических групп. Он был изобретен Хью К. Уильямсом в 1982 году.

Он хорошо работает, если число N, подлежащее факторизации, содержит один или несколько простых множителей p, так что p + 1 гладко., т.е. p + 1 содержит только маленькие множители. Он использует последовательности Люка для выполнения возведения в степень в квадратичном поле.

. Он аналогичен алгоритму p - 1 Полларда.

• 1 Алгоритм
• 2 Пример
• 3 Обобщение
• 4 Ссылки
• 5 Внешние ссылки

Выберите некоторое целое число A больше 2, которое характеризует последовательность Люка :

$V\; 0\; =\; 2,\; V\; 1\; =\; A,\; V\; j\; =\; AV\; j\; -\; 1\; -\; V\; j\; -\; 2\; \{\backslash \; displaystyle\; V\_\; \{0\}\; =\; 2,\; V\_\; \{1\}\; =\; A,\; V\_\; \{j\}\; =\; AV\_\; \{j-1\}\; -V\_\; \{j-2\}\; \}$

где все операции выполняются по модулю N.

Тогда любое нечетное простое число p делит $gcd\; (N,\; VM\; -\; 2)\; \{\backslash \; displaystyle\; \backslash \; gcd\; (N,\; V\_\; \{M\}\; -2)\; \}$когда M кратно $p\; -\; (D\; /\; p)\; \{\backslash \; displaystyle\; p-\; (D\; /\; p)\}$, где $D\; =\; A\; 2\; -\; 4\; \{\backslash \; displaystyle\; D\; =\; A\; ^\; \{2\}\; -4\}$и $(D\; /\; p)\; \{\backslash \; displaystyle\; (D\; /\; p)\}$- это Якоби символ.

Мы требуем, чтобы $(D\; /\; p)\; =\; -\; 1\; \{\backslash \; displaystyle\; (D\; /\; p)\; =\; -\; 1\}$, то есть D должен быть квадратичным неквадратичным остаток по модулю p. Но поскольку мы не знаем p заранее, перед поиском решения может потребоваться более одного значения A. Если $(D\; /\; p)\; =\; +\; 1\; \{\backslash \; displaystyle\; (D\; /\; p)\; =\; +\; 1\}$, этот алгоритм вырождается в медленную версию алгоритма p - 1 Полларда.

Итак, для разных значений M мы вычисляем $gcd\; (N,\; VM\; -\; 2)\; \{\backslash \; displaystyle\; \backslash \; gcd\; (N,\; V\_\; \{M\}\; -2)\}$, и когда результат не равен до 1 или N, мы нашли нетривиальный множитель N.

Используемые значения M являются последовательными факториалами, а $VM\; \{\backslash \; displaystyle\; V\_\; \{M\}\}$- это M-е значение последовательности, характеризующейся $VM\; -\; 1\; \{\backslash \; displaystyle\; V\_\; \{M-1\}\}$.

Чтобы найти M-й элемент V последовательности, характеризующейся B, мы переходим к аналогично возведению в степень слева направо:

x: = B y: = (B ^ 2-2) mod N для каждого бита M справа от самого старшего bit doifбит равен 1, затем x: = (x × y - B) mod N y: = (y ^ 2 - 2) mod N else y: = ( x × y - B) mod N x: = (x ^ 2 - 2) mod NV: = x

При N = 112729 и A = 5 последовательные значения $ВМ\; \{\backslash \; displaystyle\; V\_\; \{M\}\}$:

V1из seq (5) = V 1! из seq (5) = 5

V2из seq (5) = V 2! из seq (5) = 23

V3из seq (23) = V 3! из seq (5) = 12098

V4из seq (12098) = V 4! последовательности (5) = 87680

V5последовательности (87680) = V 5! последовательности (5) = 53242

V6последовательности (53242) = V 6! из seq (5) = 27666

V7из seq (27666) = V 7! из seq (5) = 110229.

В этот момент gcd (110229-2,112729) = 139, поэтому 139 - нетривиальный множитель 112729. Обратите внимание, что p + 1 = 140 = 2 × 5 × 7. Число 7! - наименьший факториал, кратный 140, поэтому на этом этапе находится правильный множитель 139.

Используя другое начальное значение, скажем A = 9, мы получаем:

V1of seq (9) = V 1! of seq (9) = 9

V2of seq ( 9) = V 2! последовательности (9) = 79

V3последовательности (79) = V 3! последовательности (9) = 41886

V4последовательности ( 41886) = V 4! последовательности (9) = 79378

V5последовательности (79378) = V 5! последовательности (9) = 1934

V6последовательности ( 1934) = V 6! последовательности (9) = 10582

V7последовательности (10582) = V 7! последовательности (9) = 84241

V8последовательности ( 84241) = V 8! последовательности (9) = 93973

V9последовательности (93973) = V 9! последовательности (9) = 91645.

При этом point gcd (91645-2,112729) = 811, поэтому 811 - нетривиальный множитель 112729. Обратите внимание, что p − 1 = 810 = 2 × 5 × 3. Число 9! - наименьший факториал, кратный 810, поэтому на этом этапе находится правильный множитель 811. На этот раз множитель 139 не найден, потому что p − 1 = 138 = 2 × 3 × 23, что не является делителем 9!

Как видно из этих примеров, мы не знаем заранее, имеет ли найденное простое число гладкое p + 1 или p − 1.

Основываясь на p - 1 Полларда и алгоритмах разложения p + 1 Вильямса, Эрик Бах и Джеффри Шаллит разработали методы эффективного разложения n при условии, что у него есть простое число. множитель p такой, что любой k циклотомический многочлен Φk(p) является гладким. Первые несколько круговых многочленов задаются последовательностью Φ 1 (p) = p − 1, Φ 2 (p) = p + 1, Φ 3 (p) = p + p + 1, и Φ 4 (p) = p + 1.

• Williams, HC (1982), «Метод факторинга p + 1», Mathematics of Computing, 39 (159): 225–234, doi : 10.2307 / 2007633, MR 0658227

• Метод факторизации P Plus 1, MersenneWiki.