Алгоритм факторизации Полларда-ро

Введение

Алгоритм целочисленной факторизации
алгоритм целочисленной факторизации

Алгоритм ро-Поларда — это алгоритм для целочисленной факторизации. Он был изобретён Джоном Поллардом в 1975 году. Он использует небольшое количество памяти, а его ожидаемое время работы пропорционально квадратному корню наименьшего простого делителя разлагаемого составного числа.

Основные идеи

Алгоритм используется для факторизации числа , где является нетривиальным фактором. Для генерации псевдослучайной последовательности используется многочлен по модулю , называемый (например, ). Важно отметить, что это должен быть именно многочлен. Выбирается начальное значение, например, 2, и последовательность продолжается как , , , и так далее. Эта последовательность связана с другой последовательностью. Поскольку неизвестно заранее, эта последовательность не может быть явно вычислена в алгоритме. Однако в ней заключается основная идея алгоритма. Поскольку число возможных значений для этих последовательностей конечно, обе последовательности – , вычисляемая по модулю , и – в конечном итоге повторятся, даже если эти значения неизвестны. Если бы последовательности вели себя как случайные числа, парадокс дней рождения подразумевает, что число шагов до повторения ожидается равным , где – число возможных значений. Таким образом, последовательность, вероятно, повторится гораздо раньше, чем последовательность. Когда найдено такое , что , но , то число является кратным , следовательно, найден фактор . После того как последовательность имеет повторяющееся значение, она становится циклической, поскольку каждое значение зависит только от предыдущего. Эта структура, приводящая к циклу, дала название алгоритму "rho", из-за сходства с формой греческой буквы ρ, когда значения , , и т. д. представлены в виде узлов в ориентированном графе. Обнаружение цикла осуществляется алгоритмом Флойда: поддерживаются два узла и (то есть, и ). На каждом шаге один узел переходит к следующему в последовательности, а другой – на два узла вперед. Затем проверяется, равно ли это 1. Если это не 1, то это означает, что в последовательности есть повторение (то есть ). Это работает, потому что если , то разность между и обязательно кратна . Хотя это всегда происходит в конечном итоге, полученный наибольший общий делитель (НОД) является делителем , отличным от 1. Это может быть само число , если обе последовательности повторяются одновременно. В этом (нечастом) случае алгоритм не удается, и его можно повторить с другим параметром.

The algorithm is used to factorize a number , where is a non trivial factor. A polynomial modulo , called (e. g., ), is used to generate a pseudorandom sequence. It is important to note that must be a polynomial. A starting value, say 2, is chosen, and the sequence continues as , , , etc. The sequence is related to another sequence Since is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet, in it lies the core idea of the algorithm. Because the number of possible values for these sequences is finite, both the sequence, which is mod , and sequence will eventually repeat, even though these values are unknown. If the sequences were to behave like random numbers, the birthday paradox implies that the number of before a repetition occurs would be expected to be , where is the number of possible values. So the sequence will likely repeat much earlier than the sequence When one has found a such that but , the number is a multiple of , so has been found. Once a sequence has a repeated value, the sequence will cycle, because each value depends only on the one before it. This structure of eventual cycling gives rise to the name "rho algorithm", owing to similarity to the shape of the Greek letter ρ when the values , , etc. are represented as nodes in a directed graph. This is detected by Floyd's cycle finding algorithm: two nodes and (i. e., and ) are kept. In each step, one moves to the next node in the sequence and the other moves forward by two nodes. After that, it is checked whether If it is not 1, then this implies that there is a repetition in the sequence (i. e. This works because if the is the same as , the difference between and is necessarily a multiple of Although this always happens eventually, the resulting greatest common divisor (GCD) is a divisor of other than 1. This may be itself, since the two sequences might repeat at the same time. In this (uncommon) case the algorithm fails, and can be repeated with a different parameter.

Варианты

В 1980 году Ричард Брент опубликовал более быструю версию алгоритма ρ. Он использовал те же основные идеи, что и Поллард, но другой метод обнаружения циклов, заменив алгоритм поиска циклов Флойда связанным методом поиска циклов Брента. Дальнейшее улучшение было предложено Полардом и Брентом. Они заметили, что если , то также для любого положительного целого числа b. В частности, вместо вычисления на каждом шаге, достаточно определить z как произведение 100 последовательных значений по модулю n, а затем вычислить один gcd. Это значительно ускоряет работу, поскольку 100 операций gcd заменяются 99 умножениями по модулю n и одной операцией gcd. Иногда это может привести к неудаче алгоритма из-за появления повторяющегося множителя, например, когда n является квадратом. Но в этом случае достаточно вернуться к предыдущему значению gcd, где , и продолжить использование стандартного алгоритма ρ с этого момента.

Применение

Алгоритм очень быстрый для чисел с малыми факторами, но замедляется в случаях, когда все факторы велики. Наиболее заметным успехом алгоритма ρ стало разложение на множители числа Ферма F8 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321 в 1980 году. Алгоритм ρ был удачным выбором для F8, поскольку простой множитель p = 1238926361552897 значительно меньше другого множителя. Разложение заняло 2 часа на компьютере UNIVAC 1100/42.