Williamss п + 1 алгоритм - Williamss p + 1 algorithm

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

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

Это аналог Полларда п - 1 алгоритм.

Алгоритм

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

${\displaystyle V_{0}=2,V_{1}=A,V_{j}=AV_{j-1}-V_{j-2}}$

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

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

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

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

Ценности M используются последовательные факториалы, и ${\displaystyle V_{M}}$ это M-е значение последовательности, характеризуемой ${\displaystyle V_{M-1}}$.

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

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

Пример

С N= 112729 и А= 5, последовательные значения ${\displaystyle V_{M}}$ находятся:

V₁ из seq (5) = V_1! из seq (5) = 5

V₂ из seq (5) = V_2! из seq (5) = 23

V₃ из seq (23) = V_3! из seq (5) = 12098

V₄ из seq (12098) = V_4! из seq (5) = 87680

V₅ из seq (87680) = V_5! из seq (5) = 53242

V₆ из seq (53242) = V_6! из seq (5) = 27666

V₇ из seq (27666) = V_7! из seq (5) = 110229.

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

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

V₁ из seq (9) = V_1! из seq (9) = 9

V₂ из seq (9) = V_2! из seq (9) = 79

V₃ из seq (79) = V_3! из seq (9) = 41886

V₄ из seq (41886) = V_4! из seq (9) = 79378

V₅ из seq (79378) = V_5! из seq (9) = 1934

V₆ из seq (1934) = V_6! из seq (9) = 10582

V₇ из seq (10582) = V_7! из seq (9) = 84241

V₈ из seq (84241) = V_8! из seq (9) = 93973

V₉ из seq (93973) = V_9! из seq (9) = 91645.

В этот момент 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.

Обобщение

На основе Полларда п − 1 и Уильямса п+1 алгоритмы факторинга, Эрик Бах и Джеффри Шаллит разработали методы факторизации п эффективно при условии, что у него есть главный фактор п такой, что любой k^th циклотомический многочлен Φ_k(п) является гладкий.^[1]Первые несколько круговых полиномов задаются последовательностью Φ₁(п) = п−1, Φ₂(п) = п+1, Φ₃(п) = п²+п+1, а Φ₄(п) = п²+1.

Рекомендации

1. Бах, Эрик; Шаллит, Джеффри (1989). «Факторинг с циклотомическими многочленами» (PDF). Математика вычислений. Американское математическое общество. 52 (185): 201–219. Дои:10.1090 / S0025-5718-1989-0947467-1. JSTOR  2008664.

• Уильямс, Х. С. (1982), "Метод факторинга p + 1", Математика вычислений, 39 (159): 225–234, Дои:10.2307/2007633, МИСТЕР  0658227

внешняя ссылка

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