Опросы п - 1 алгоритм - Pollards p − 1 algorithm - Wikipedia

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

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

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

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

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

Если число Икс конгруэнтно 1 по модулю фактор п, то gcd (Икс − 1, п) будет делиться на этот коэффициент.

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

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

Возможно, что для всех простых факторов п из п, п - 1 делится на маленькие простые числа, в этом случае число Полларда п - 1 алгоритм дает вам п опять таки.

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

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

Входы: п: составное число
Выход: нетривиальный фактор п или же отказ
  1. выберите границу гладкости B
  2. определять (примечание: явная оценка M может не понадобиться)
  3. случайно выбрать а взаимно простой с п (примечание: мы можем исправить а, например если п нечетно, то всегда можно выбрать а = 2, случайный выбор здесь не обязателен)
  4. вычислить грамм = gcd (аM − 1, п) (примечание: возведение в степень можно выполнить по модулюп)
  5. если 1 < грамм < п затем вернись грамм
  6. если грамм = 1 затем выберите больший B и перейдите к шагу 2 или вернитесь отказ
  7. если грамм = п затем выберите меньший B и перейдите к шагу 2 или вернитесь отказ

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

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

Пример

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

  1. Мы выбираем B = 5.
  2. Таким образом M = 22 × 31 × 51.
  3. Мы выбираем а = 2.
  4. грамм = gcd (аM − 1, п) = 13.
  5. Поскольку 1 <13 <299, верните 13.
  6. 299/13 = 23 простое число, поэтому оно полностью разложено на множители: 299 = 13 × 23.

Как выбрать B?

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

Предположить, что п - 1, где п наименьший простой делитель п, можно смоделировать как случайное число размером меньшеп. По теореме Диксона вероятность того, что наибольший множитель такого числа меньше (п − 1)1 / ε примерно εε; так что есть вероятность около 3−3 = 1/27, что a B значение п1/6 даст факторизацию.

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

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

Иногда используется вариант основного алгоритма; вместо того, чтобы требовать этого п - 1 имеет все факторы меньше, чем B, мы требуем, чтобы все его факторы, кроме одного, были меньше, чем некоторые B1, а оставшийся множитель меньше некоторых B2B1. После завершения первого этапа, аналогичного базовому алгоритму, вместо вычисления нового

за B2 и проверка gcd (аM ' − 1, п), мы вычисляем

куда ЧАС = аM и проверьте, если gcd (Q, п) дает нетривиальный множитель п. Как и раньше, возведение в степень можно производить по модулюп.

Позволять {q1, q2,…} - последовательные простые числа в интервале (B1, B2] и dп = qп − qп−1 разница между последовательными простыми числами. Поскольку обычно B1 > 2, dп четные числа. Распределение простых чисел таково, что dп все будет относительно маленьким. Предполагается, что dппер2 B2. Следовательно, значения ЧАС2, ЧАС4, ЧАС6,… (Модп) можно сохранить в таблице, а ЧАСqп вычисляться из ЧАСqп−1ЧАСdп, избавляя от необходимости возведения в степень.

Реализации

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

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

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