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

Специальный алгоритм факторизации целых чисел

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

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

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

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

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

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

Если число x сравнимо с 1 по модулю множителя n , то наибольший общий делитель ( x − 1, n ) будет делиться на этот множитель.

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

Множественные факторы

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

Алгоритм и время выполнения

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

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

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

1. выберите границу гладкости B
2. определить (примечание: явная оценка M может не потребоваться) ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }}$
3. случайным образом выбрать положительное целое число a , которое взаимно просто с n (примечание: на самом деле мы можем зафиксировать a , например, если n нечетное, то мы всегда можем выбрать a = 2, случайный выбор здесь не обязателен)
4. вычислить g = gcd( a ^M − 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 -powersmooth. Если g = n на шаге 7, это обычно означает, что все множители были B -powersmooth, но в редких случаях это может означать, что a имеет малый порядок по модулю  n . Кроме того, когда максимальные простые множители p-1 для каждого простого множителя p из n в некоторых редких случаях все одинаковы, этот алгоритм потерпит неудачу.

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

Пример

Если мы хотим разложить на множители число n = 299.

1. Мы выбираем B = 5.
2. Таким образом, М = 2 ² × 3 ¹ × 5 ¹ .
3. Мы выбираем а = 2.
4. g = gcd( a ^M − 1, n ) = 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 ₁ . После завершения первого этапа, который совпадает с базовым алгоритмом, вместо вычисления нового

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

для B ₂ и проверяя gcd( a ^M' − 1, n ) , мы вычисляем

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

где H = a ^M и проверьте, производит ли 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 ² B ₂ . Следовательно, значения H ² , H ⁴ , H ⁶ , … (mod  n ) можно сохранить в таблице, а H ^{q _n} вычислить из H ^{q _{n −1}} ⋅ H ^{d _n} , избавляя от необходимости возведения в степень.

Реализации

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

Смотрите также

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

Ссылки

1. Что такое сильные простые числа и необходимы ли они для системы RSA?, RSA Laboratories (2007)

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