Алгоритм Rho Полларда является алгоритм для целочисленной факторизации . Он был изобретен Джоном Pollard в 1975 г. [1] Он использует только небольшое количество пространства, и его ожидаемое время работы пропорциональна корню квадратному из размера наименьшего главного фактора из составного числа будучи разложено.
Основные идеи
Алгоритм используется для факторизации числа , где - нетривиальный фактор. Полином по модулю, называется (например, ), используется для генерации псевдослучайной последовательности : выбирается начальное значение, скажем 2, и последовательность продолжается как, , и т. д. Последовательность связана с другой последовательностью . Сзаранее не известно, эта последовательность не может быть явно вычислена в алгоритме. Тем не менее, в этом заключается основная идея алгоритма.
Поскольку количество возможных значений для этих последовательностей конечно, оба последовательность, которая является мод , а также последовательность в конечном итоге повторится, даже если эти значения неизвестны. Если бы последовательности вели себя как случайные числа, парадокс дня рождения подразумевает, что количество до того, как произойдет повторение, ожидается , где - количество возможных значений. Итак, последовательность скорее всего, повторится намного раньше, чем последовательность . Как только последовательность имеет повторяющееся значение, последовательность будет циклически повторяться, потому что каждое значение зависит только от предыдущего. Эта структура возможного цикла дает название «алгоритм Ро» из-за сходства с формой греческого символа ρ, когда значения, и т. д. представлены как узлы в ориентированном графе .
Это обнаруживается алгоритмом поиска цикла Флойда : два узла а также (т.е. а также ) хранятся. На каждом шаге один перемещается к следующему узлу в последовательности, а другой перемещается вперед на два узла. После этого проверяется, не. Если это не 1, то это означает, что есть повторение в последовательность (т.е. . Это работает, потому что если такой же как , разница между а также обязательно кратно . Хотя это всегда происходит в конце концов, полученный наибольший общий делитель (НОД) является делителем кроме 1. Это может быть сам по себе, поскольку две последовательности могут повторяться одновременно. В этом (редком) случае алгоритм не работает, и его можно повторить с другим параметром.
Алгоритм
Алгоритм принимает на вход n , целое число, которое нужно разложить на множители; а также, многочлен от x, вычисленный по модулю n . В исходном алгоритме, но в настоящее время более распространено использование . На выходе либо нетривиальный множитель n , либо сбой. Он выполняет следующие шаги: [2]
х ← 2 y ← 2 г ← 1 а d = 1: х ← г (х) у ← г (г (у)) d ← НОД (| x - y |, n) если d = n: вернуть ошибку else : вернуть d
Здесь x и y соответствуют а также в разделе об основной идее. Обратите внимание, что этот алгоритм может не найти нетривиальный множитель, даже если n составное. В этом случае метод можно попробовать еще раз, используя начальное значение, отличное от 2, или другое.
Пример факторизации
Позволять а также .
я | Икс | у | НОД (| x - y |, 8051) |
---|---|---|---|
1 | 5 | 26 год | 1 |
2 | 26 год | 7474 | 1 |
3 | 677 | 871 | 97 |
4 | 7474 | 1481 | 1 |
97 - нетривиальный множитель 8051. Начальные значения, отличные от x = y = 2, могут давать кофактор (83) вместо 97. Одна дополнительная итерация показана выше, чтобы прояснить, что y перемещается в два раза быстрее, чем x . Обратите внимание, что даже после повторения НОД может вернуться к 1.
Варианты
В 1980 году Ричард Брент опубликовал более быстрый вариант алгоритма ро. Он использовал те же основные идеи, что и Поллард, но другой метод обнаружения циклов, заменив алгоритм поиска циклов Флойда родственным методом поиска циклов Брента . [3]
Дальнейшее улучшение было сделано Поллардом и Брентом. Они заметили, что если, то также для любого положительного целого числа . В частности, вместо вычисления на каждом шагу достаточно определить как результат 100 последовательных члены по модулю , а затем вычислить один . Значительное ускорение результатов, так как шаги 100 gcd заменены 99 умножениями по модулюи один gcd . Иногда это может привести к сбою алгоритма из-за введения повторяющегося фактора, например, когдаэто квадрат. Но тогда достаточно вернуться к предыдущему члену gcd , где, и оттуда воспользуемся обычным ρ-алгоритмом.
Заявление
Алгоритм очень быстр для чисел с маленькими множителями, но медленнее в случаях, когда все множители большие. Самым замечательным успехом алгоритма ρ была факторизация числа Ферма F 8 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321. [4] Алгоритм ρ был хорошим выбором для F 8, потому что простой фактор p = 1238926361552897 намного меньше, чем другой множитель. Факторизация на UNIVAC 1100/42 заняла 2 часа . [4]
Пример n = 10403 = 101 · 103
В этом примере вычисляется только одна последовательность, а НОД вычисляется внутри цикла, который определяет цикл.
Пример кода C
В следующем примере кода определяется коэффициент 101 из 10403 с начальным значением x = 2.
#include #include int gcd ( int a , int b ) { int остаток ; while ( b ! = 0 ) { остаток = a % b ; а = б ; b = остаток ; } Вернуть ; }int main ( int argc , char * argv []) { int number = 10403 , loop = 1 , count ; int x_fixed = 2 , x = 2 , size = 2 , factor ; do { printf ( "---- цикл% 4i ---- \ n " , цикл ); count = размер ; do { x = ( x * x + 1 ) % число ; factor = gcd ( abs ( x - x_fixed ), number ); printf ( "count =% 4i x =% 6i factor =% i \ n " , size - count + 1 , x , factor ); } while ( - count && ( factor == 1 )); размер * = 2 ; x_fixed = x ; петля = петля + 1 ; } while ( коэффициент == 1 ); printf ( "коэффициент равен% i \ n " , коэффициент ); коэффициент возврата == число ? EXIT_FAILURE : EXIT_SUCCESS ; }
Приведенный выше код покажет ход выполнения алгоритма, а также промежуточные значения. Конечная строка вывода будет «коэффициент 101». Код будет работать только для небольших тестовых значений, поскольку в целочисленных типах данных во время квадрата x произойдет переполнение.
Пример кода Python
из itertools счетчик импорта из математического импорта gcd import sys число , x = 10403 , 2для цикла в count ( 1 ): y = x для i в диапазоне ( 2 ** цикл ): x = ( x * x + 1 ) % number factor = gcd ( x - y , number ) если factor > 1 : print ( "фактор есть" , фактор ) sys . выход ()
Результаты
В следующей таблице третий и четвертый столбцы содержат секретную информацию, неизвестную человеку, пытающемуся вычислить коэффициент pq = 10403. Они включены, чтобы показать, как работает алгоритм. Начиная с x = 2, алгоритм выдает следующие числа:
шаг | ||||
---|---|---|---|---|
2 | 2 | 2 | 2 | 0 |
5 | 2 | 5 | 2 | 1 |
26 год | 2 | 26 год | 2 | 2 |
677 | 26 год | 71 | 26 год | 3 |
598 | 26 год | 93 | 26 год | 4 |
3903 | 26 год | 65 | 26 год | 5 |
3418 | 26 год | 85 | 26 год | 6 |
156 | 3418 | 55 | 85 | 7 |
3531 | 3418 | 97 | 85 | 8 |
5168 | 3418 | 17 | 85 | 9 |
3724 | 3418 | 88 | 85 | 10 |
978 | 3418 | 69 | 85 | 11 |
9812 | 3418 | 15 | 85 | 12 |
5983 | 3418 | 24 | 85 | 13 |
9970 | 3418 | 72 | 85 | 14 |
236 | 9970 | 34 | 72 | 15 |
3682 | 9970 | 46 | 72 | 16 |
2016 г. | 9970 | 97 | 72 | 17 |
7087 | 9970 | 17 | 72 | 18 |
10289 | 9970 | 88 | 72 | 19 |
2594 | 9970 | 69 | 72 | 20 |
8499 | 9970 | 15 | 72 | 21 год |
4973 | 9970 | 24 | 72 | 22 |
2799 | 9970 | 72 | 72 | 23 |
Первое повторение по модулю 101 - 97, которое происходит на этапе 17. Повторение не обнаруживается до этапа 23, когда . Это вызывает быть , и фактор найден.
Сложность
Если псевдослучайное число встречающиеся в алгоритме Полларда ρ были фактическим случайным числом, из этого следует, что успех будет достигнут в половине случаев, по парадоксу дня рождения витераций. Считается, что тот же анализ применим и к реальному алгоритму ро, но это эвристическое утверждение, и тщательный анализ алгоритма остается открытым. [5]
Смотрите также
Рекомендации
- Перейти ↑ Pollard, JM (1975). «Метод Монте-Карло для факторизации». BIT Численная математика . 15 (3): 331–334. DOI : 10.1007 / bf01933667 .
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. и Стейн, Клиффорд (2009). «Раздел 31.9: Целочисленная факторизация». Введение в алгоритмы (третье изд.). Кембридж, Массачусетс: MIT Press. С. 975–980. ISBN 978-0-262-03384-8. CS1 maint: обескураженный параметр ( ссылка ) (в этом разделе обсуждается только алгоритм ро Полларда).
- ^ Брент, Ричард П. (1980). «Улучшенный алгоритм факторизации Монте-Карло» . БИТ . 20 : 176–184. DOI : 10.1007 / BF01933190 . CS1 maint: обескураженный параметр ( ссылка )
- ^ а б Brent, RP; Поллард, Дж. М. (1981). «Факторизация восьмого числа Ферма» . Математика вычислений . 36 (154): 627–630. DOI : 10.2307 / 2007666 .
- ^ Гэлбрейт, Стивен Д. (2012). «14.2.5 На пути к тщательному анализу Полларда ро». Математика криптографии с открытым ключом . Издательство Кембриджского университета. С. 272–273. ISBN 9781107013926..
дальнейшее чтение
- Кац, Джонатан; Линделл, Иегуда (2007). «Глава 8». Введение в современную криптографию . CRC Press.
- Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. С. 135–138. ISBN 978-1-4704-1048-3.
Внешние ссылки
- Подробная статья об алгоритме Полларда Rho, предназначенная для аудитории начального уровня.
- Вайсштейн, Эрик В. "Метод факторизации ро Полларда" . MathWorld .
- Реализация Java
- О Поллард Ро