Pollard's $\rho$ method factors $n$ by iterating a "random-looking" function such as $f(x) = x^2 + 1 \pmod n$ from a starting point $x_0$. A tortoise walks the sequence one step at a time ($x_i$) and a rabbit two steps at a time ($x_{2i}$). After each step we compute $\gcd(x_{2i} - x_i,\, n)$. If it is a proper factor: yay! If it is $1$: keep going. If it is $n$: stop, fail (try another $x_0$ or $c$).
try:
The picture: why it is called $\rho$
The sequence can only take finitely many values, so it eventually repeats: a tail, then a cycle, shaped like the Greek letter $\rho$. The rabbit gains one step on the tortoise every turn, so once both are on the cycle the rabbit catches up.
Why does this work?
- By the Chinese Remainder Theorem, the sequence mod $n = pq$ is really two sequences at once: one mod $p$ and one mod $q$. Each has its own, much smaller $\rho$ (roughly $\sqrt p$ and $\sqrt q$ long, by the birthday paradox).
- If the tortoise and rabbit coincide mod $p$ but not mod $q$, then $p \mid x_{2i} - x_i$ but $q \nmid x_{2i} - x_i$, so $\gcd(x_{2i} - x_i, n) = p$. We never needed to know $p$ in advance!
- If they coincide mod $p$ and mod $q$ at the same step, the gcd is $n$ and the method fails; try a different $x_0$ or $c$ (the "299" example).
- The expected number of steps is about $\sqrt p$ for the smallest prime factor $p$, so an RSA modulus with two 100-digit primes would take around $10^{50}$ steps. See the textbook, Section 3.8.1 (Pollard's $\rho$ factoring method), and the Pollard Rho Sage page.