# Pollard's Rho factoring An algorithm for factoring large integer $n$ more specific, finding $p$ s.t., $p|n$. From [^1]: A random sequence in modulo $n$ will repeat itself at some point. This happen when the difference between their indices is a factor of $n$. If $p|n$ then it is highly probable that this difference is actually a factor of $p$ which is smaller than $n$. This means that this difference is a factor of $n$ as needed. More details. we start with a random value $x_1$. We generate a pseudo random sequence using the recursive formula $x_i=x_{i-1}^2 -1\bmod n$. At some point the sequence repeat itself into a cycle with length lt;n$. The size of this cycle is not known in advanced but it is bounded by some power of 2. We start with cycle of size 2 . In each iteration $i$, we initially set $y=x_{2^i}$ and forward $x_i$ by $2^i$ steps. Eventually, $x_i$ should collide with $y$. For each step we check if $\gcd(y-x_i,n)>1$ (i.e., if $\gcd$ is different than $n$) i.e., if $y$ and $x_i$ collide in $[0,p)$ for $p<n$. Let's see how the sequence modulo $n$ is actually a sequence modulo $p|n$: Let $x'_i =x_i\bmod p$ , then we have: $ \begin{align} x'_{i+1} &= x_{i+1} \bmod p \\ & = (x_i^2-1 \bmod n)\bmod p\\ & = x_i^2-1 \bmod p\\ & = ((x_i\bmod p)^2 -1)\bmod p\\ & = ({x'_i})^2 -1\bmod p \\ \end{align} $ This means that a pseudo random walk in $[0,n)$ can also be seen as a random walk in $[0,p)$ for every $p|n$. "Collision" in a smaller range has higher probability than larger ones due to the [[The Birthday Paradox]] . The probability of the first is $O(\sqrt p)$ while the second is $O(\sqrt n)$ and $p\ll n$. Note that $y\equiv x_i\bmod n$ derive that $y\equiv x_i \bmod p$. ![[Pasted image 20250608192812.png|300]] ![[Pasted image 20250609092354.png|500]] References: [video1](https://www.youtube.com/watch?v=6khEMeU8Fck) , [video2](https://www.youtube.com/watch?v=PYmXv4lqSPY), [blog](https://home.cs.colorado.edu/~srirams/courses/csci2824-spr14/pollardsRho.html) ## Created 2024-11-19 17:56 [^1]: [Introduction to Algorithms (Cormen)](http://139.59.56.236/bitstream/123456789/106/1/Introduction%20to%20Algorithms%20by%20Thomas%20%20H%20Coremen.pdf#page=997) , page 997