Алгоритм Полларда p - 1

Алгоритм Полларда p - 1 — это теоретико-числовой факторизации целых чисел алгоритм , изобретенный Джоном Поллардом в 1974 году. Это алгоритм специального назначения, что означает, что он подходит только для целых чисел с определенными типами факторов; это простейший пример алгоритма факторизации алгебраической группы .

Факторы, которые он находит, - это те, для которых число, предшествующее фактору, p - 1, является степенным ; существенное наблюдение состоит в том, что, работая в мультипликативной группе по модулю составного числа N , мы также работаем в мультипликативных группах по модулю всех N множителей.

Существование этого алгоритма приводит к понятию безопасных простых чисел , которые представляют собой простые числа, для которых p - 1 дважды является простым числом Софи Жермен q и, следовательно, минимально гладкими. Эти простые числа иногда рассматриваются как «безопасные для криптографических целей», но они могут быть небезопасными — в текущих рекомендациях для криптографически сильных простых чисел ( например, ANSI X9.31 ) необходимо, но недостаточно , чтобы p − 1 имело хотя бы одно большое простое число. фактор. Большинство достаточно больших простых чисел являются сильными; если простое число, используемое в криптографических целях, окажется ненадежным, то это, скорее всего, произойдет по злому умыслу, чем по ошибке генерации случайных чисел . Эта терминология считается устаревшей в криптографической отрасли: метод факторизации ECM более эффективен, чем алгоритм Полларда, и находит безопасные простые множители так же быстро, как и небезопасные простые множители аналогичного размера, поэтому размер p является ключевым параметром безопасности. , а не гладкость p-1 .

Базовые концепции

Пусть n — составное целое число с простым множителем p . По малой теореме Ферма мы знаем, что для всех целых чисел, взаимно простых с p, и для всех натуральных чисел K :

$a^{K(p-1)}\equiv 1{\pmod {p}}$

Если число x конгруэнтно 1 по модулю фактора n , то НОД ( x − 1, n ) будет делиться на этот фактор.

Идея состоит в том, чтобы сделать показатель степени кратным p - 1, сделав его числом с очень большим количеством простых множителей; обычно мы берем произведение всех степеней простых чисел меньше некоторого предела B . Начните со случайного x и неоднократно заменяйте его на $x^{w}{\bmod {n}}$ поскольку w проходит через эти основные степени. Проверяйте на каждом этапе или один раз в конце, если хотите, ли gcd( x − 1, n ) не равен 1.

Несколько факторов

Вполне возможно, что для всех простых множителей числа n p p − 1 делится на маленькие простые числа, и в этот момент алгоритм Полларда p − 1 просто возвращает n .

Алгоритм и время работы

Основной алгоритм можно записать следующим образом:

Входные данные : n : составное число.

Выход : нетривиальный фактор n или отказ.

1. выберите границу гладкости B
2. определять $M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }$ (примечание: явное вычисление M может не потребоваться)
3. случайным образом выбрать положительное целое число a , которое взаимно просто с n (примечание: на самом деле мы можем зафиксировать a , например, если n нечетное, то мы всегда можем выбрать a = 2, случайный выбор здесь не обязателен)
4. вычислить g = НОД( a ^М − 1, n ) (примечание: возведение в степень можно выполнить по модулю n )
5. если 1 < g < n, то вернуть g
6. если g = 1 , выберите больший B и перейдите к шагу 2 или верните ошибку.
7. если g = n , выберите меньший B и перейдите к шагу 2 или верните ошибку.

Если g = 1 на шаге 6, это означает, что не существует простых множителей p, для которых p-1 является B -степенным гладким. Если g = n на шаге 7, это обычно указывает на то, что все факторы были B -степенно гладкими, но в редких случаях это может указывать на то, что a имеет малый порядок по модулю n . Кроме того, когда в некоторых редких случаях максимальные простые множители p-1 для каждого простого множителя p из n одинаковы, этот алгоритм потерпит неудачу.

Время работы этого алгоритма составляет O( B × log B × log ² п ) ; большие значения B заставляют его работать медленнее, но с большей вероятностью создают коэффициент.

Пример

Если мы хотим факторизовать число n = 299.

1. Выбираем В = 5.
2. Таким образом, М = 2 ² × 3 ¹ × 5 ¹ .
3. Выбираем а = 2.
4. g = НОД( а ^М − 1, п ) = 13.
5. Поскольку 1 < 13 < 299, верните 13.
6. 299/13 = 23 — простое число, поэтому оно полностью факторизовано: 299 = 13 × 23.

Методы выбора Б

Поскольку алгоритм является инкрементным, он может продолжать работать с постоянно увеличивающейся границей.

Предположим, что p − 1, где p — наименьший простой делитель числа n , можно смоделировать как случайное число размером меньше √ n . По теореме Диксона вероятность того, что наибольший делитель такого числа меньше ( p − 1) ^1/е примерно равно ε ^{− е} ; так что вероятность около 3 ⁻³ = 1/27, что B значение n ^1/6 даст факторизацию.

На практике метод эллиптических кривых работает быстрее, чем метод Полларда p - 1, если факторы вообще велики; выполнение метода p - 1 до B = 2 ³² найдет четверть всех 64-битных факторов и 1/27 всех 96-битных факторов.

Двухступенчатый вариант

Иногда используется вариант основного алгоритма; вместо того, чтобы требовать, чтобы все факторы p − 1 были меньше B , мы требуем, чтобы все факторы, кроме одного, были меньше некоторого B ₁ , а оставшийся фактор был меньше некоторого B ₂ ≫ B ₁ . После завершения первого этапа, аналогичного базовому алгоритму, вместо вычисления нового

$M'=\prod _{{\text{primes }}q\leq B_{2}}q^{\lfloor \log _{q}B_{2}\rfloor }$

для B ₂ и проверка НОД( a ^М' − 1, n ) , мы вычисляем

$Q=\prod _{{\text{primes }}q\in (B_{1},B_{2}]}(H^{q}-1)$

где Н = а ^М и проверьте, создает ли gcd( Q , n ) нетривиальный множитель n . Как и раньше, возведение в степень можно выполнять по модулю n .

Пусть { q ₁ , q ₂ , …} — последовательные простые числа в интервале ( B ₁ , B ₂ ] и d _n = q _n − q _{n −1 —} разность между последовательными простыми числами. Поскольку обычно B ₁ > 2 , d _n — четные числа. Распределение простых чисел таково, что все d _n будут относительно малы. Предполагается, что d _n ≤ ln. ² Б ₂ . Следовательно, значения H ² , Ч ⁴ , Ч ⁶ , … (mod n ) можно хранить в таблице, а H ^{q _н} быть вычислено из H ^{q _{п -1}} ⋅ H ^{д _н} , сохраняя необходимость возведения в степень.

Реализации

• Пакет GMP-ECM включает эффективную реализацию метода p - 1.
• Prime95 и MPrime , официальные клиенты Great Internet Mersenne Prime Search , используют модифицированную версию алгоритма p-1 для исключения потенциальных кандидатов.

См. также

• Алгоритм Уильямса p + 1

Ссылки

• Поллард, Дж. М. (1974). «Теоремы факторизации и проверки простоты». Труды Кембриджского философского общества . 76 (3): 521–528. Бибкод : 1974PCPS...76..521P . дои : 10.1017/S0305004100049252 . S2CID   122817056 .
• Монтгомери, Польша; Сильверман, Р.Д. (1990). «Расширение БПФ алгоритма факторинга P - 1» . Математика вычислений . 54 (190): 839–854. Бибкод : 1990MaCom..54..839M . дои : 10.1090/S0025-5718-1990-1011444-3 .
• Сэмюэл С. Вагстафф-младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. стр. 138–141. ISBN  978-1-4704-1048-3 .