Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the composite number being factorized.
Core ideas The algorithm is used to factorize a number n = p q {\displaystyle n=pq} , where p {\displaystyle p} is a non-trivial factor. A polynomial modulo n {\displaystyle n} , called g ( x ) {\displaystyle g(x)} (e.g., g ( x ) = ( x 2 + 1 ) mod n {\displaystyle g(x)=(x^{2}+1){\bmod {n}}} ), is used to generate a pseudorandom sequence. g ( x ) {\displaystyle g(x)} must be a polynomial. A starting value, say 2, is chosen, and the sequence continues as x 1 = g ( 2 ) {\displaystyle x_{1}=g(2)} , x 2 = g ( g ( 2 ) ) {\displaystyle x_{2}=g(g(2))} , x 3 = g ( g ( g ( 2 ) ) ) {\displaystyle x_{3}=g(g(g(2)))} , etc. The sequence is related to another sequence { x k mod p } {\displaystyle \{x_{k}{\bmod {p}}\}} . Since p {\displaystyle p} 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 { x k } {\displaystyle \{x_{k}\}} sequence, which is mod n {\displaystyle n} , and { x k mod p } {\displaystyle \{x_{k}{\bmod {p}}\}} 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 x k {\displaystyle x_{k}} before a repetition occurs would be expected to be O ( N ) {\displaystyle O({\sqrt {N}})} , where N {\displaystyle N} is the number of possible values. So the sequence { x k mod p } {\displaystyle \{x_{k}{\bmod {p}}\}} will likely repeat much earlier than the sequence { x k } {\displaystyle \{x_{k}\}} . When one has found a k 1 , k 2 {\displaystyle k_{1},k_{2}} such that x k 1 ≠ x k 2 {\displaystyle x_{k_{1}}\neq x_{k_{2}}} but x k 1 ≡ x k 2 mod p {\displaystyle x_{k_{1}}\equiv x_{k_{2}}{\bmod {p}}} , the number | x k 1 − x k 2 | {\displaystyle |x_{k_{1}}-x_{k_{2}}|} is a multiple of p {\displaystyle p} , so a non-trivial divisor 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 x 1 mod p {\displaystyle x_{1}{\bmod {p}}} , x 2 mod p {\displaystyle x_{2}{\bmod {p}}} , etc. are represented as nodes in a directed graph.
… excerpt ends here. Continue reading the full article.
