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

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

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

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

Алгоритм

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

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

Тогда любое нечетное простое число п разделяет в любое время M кратно , куда и это Символ Якоби.

Мы требуем, чтобы , то есть, D должен быть квадратичный невычет по модулю п. Но как мы не знаем п заранее, более одного значения А может потребоваться перед поиском решения. Если , этот алгоритм вырождается в медленную версию Алгоритм Полларда p - 1.

Итак, для разных значений M мы рассчитываем , а когда результат не равен 1 или N, мы нашли нетривиальный множитель N.

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

Чтобы найти 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, последовательные значения находятся:

V1 из seq (5) = V1! из seq (5) = 5
V2 из seq (5) = V2! из seq (5) = 23
V3 из seq (23) = V3! из seq (5) = 12098
V4 из seq (12098) = V4! из seq (5) = 87680
V5 из seq (87680) = V5! из seq (5) = 53242
V6 из seq (53242) = V6! из seq (5) = 27666
V7 из seq (27666) = V7! из seq (5) = 110229.

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

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

V1 из seq (9) = V1! из seq (9) = 9
V2 из seq (9) = V2! из seq (9) = 79
V3 из seq (79) = V3! из seq (9) = 41886
V4 из seq (41886) = V4! из seq (9) = 79378
V5 из seq (79378) = V5! из seq (9) = 1934
V6 из seq (1934) = V6! из seq (9) = 10582
V7 из seq (10582) = V7! из seq (9) = 84241
V8 из seq (84241) = V8! из seq (9) = 93973
V9 из seq (93973) = V9! из seq (9) = 91645.

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

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

Обобщение

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

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

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

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