Опросы п - 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 алгоритм дает вам п опять таки.
Алгоритм и время работы
Базовый алгоритм можно записать следующим образом:
- Входы: п: составное число
- Выход: нетривиальный фактор п или же отказ
- выберите границу гладкости B
- определять (примечание: явная оценка M может не понадобиться)
- случайно выбрать а взаимно простой с п (примечание: мы можем исправить а, например если п нечетно, то всегда можно выбрать а = 2, случайный выбор здесь не обязателен)
- вычислить грамм = gcd (аM − 1, п) (примечание: возведение в степень можно выполнить по модулюп)
- если 1 < грамм < п затем вернись грамм
- если грамм = 1 затем выберите больший B и перейдите к шагу 2 или вернитесь отказ
- если грамм = п затем выберите меньший B и перейдите к шагу 2 или вернитесь отказ
Если грамм = 1 на шаге 6 это означает, что нет простых множителей п для которого п-1 является B-powersmooth. Если грамм = п на шаге 7 это обычно означает, что все факторы были B-powersmooth, но в редких случаях может указывать на то, что а имел небольшой порядок по модулюп. Кстати, когда максимальные простые множители п-1 для каждого простого фактора п из п все одинаковы, в некоторых редких случаях этот алгоритм не сработает.
Время работы этого алгоритма O (B × журнал B × журнал2 п); большие значения B заставить его работать медленнее, но с большей вероятностью создаст фактор.
Пример
Если мы хотим разложить число п = 299.
- Мы выбираем B = 5.
- Таким образом M = 22 × 31 × 51.
- Мы выбираем а = 2.
- грамм = gcd (аM − 1, п) = 13.
- Поскольку 1 <13 <299, верните 13.
- 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, а оставшийся множитель меньше некоторых B2 ≫ B1. После завершения первого этапа, аналогичного базовому алгоритму, вместо вычисления нового
за 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п, избавляя от необходимости возведения в степень.
Реализации
- В GMP-ECM пакет включает эффективную реализацию п - 1 метод.
- Prime95 и MPrime, официальные клиенты Отличный интернет-поиск Mersenne Prime используйте модифицированную версию алгоритма p - 1 для исключения потенциальных кандидатов.
Смотрите также
Рекомендации
- ^ Что такое сильные простые числа и необходимы ли они для системы RSA?, Лаборатории RSA (2007)
- Поллард, Дж. М. (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.