## Problem

Extract an arbitrary non-trivial factor of a given integer $$n$$.

## Prerequisite

Miller-Rabin Primality Test

## Pollard-Rho

Let’s consider a pseudo-random polynomial function $$f_n : Z_n \rightarrow Z_n$$, where $$f_n(x) \equiv x^2 + 1\pmod n$$.

Consider starting with a random seed $$s_{n, 0}$$. We can define the sequence in the form of linear recurrence: $$s_{n, i} = f_n(s_{n, i - 1})$$.

The Birthday Paradox states that, given that there are $$d$$ days in a year, with $$O(n^{0.5})$$ people there is roughly a $$50\%$$ chance that there is at least a pair with the same birthday. Since we may assume that $$s_n$$ is a random sequence, the birthday paradox enlightens that it is likely there is some pair of elements in the first $$O(n^{0.5})$$ elements of the sequence. The distance between them is the period of the sequence. You may think of the Greek letter $$\rho$$, where the cycle has length of the distance.

Up to now, we do not see anything that directly serves the purpose, and the complexity ($$O(n^{0.5})$$) is not good.

Let us consider $$n = p\times q$$, where $$p > 1 \land q > 1$$. Without loss of generality, we may assume that $$p \leq q$$.

Instead of looking at sequence $$s_n$$, let us see what $$s_p$$ can do for us. We may discover that the expected length of cycle of the sequence $$s_p$$ is $$O(p^{0.5}) \leq O(n^{0.25})$$. Although we have no clue what $$p$$ could be at this moment, we are still able to proceed, since we can expect that by $$O(n^{0.25})$$ cost we can find some two distinct indices $$i$$ and $$j$$ that satisfies $$s_{p, i} \equiv s_{p, j} \pmod p$$. This implies that $$s_{n, i} \equiv s_{n, j} \pmod p$$, where the probability that $$s_{n, i} \equiv s_{n, j} \pmod n$$ is $$q^{-1}$$ (assuming $$s$$ is somewhat uniformly distributed). Hence, there is only $$q^{-1} \leq n^{-0.5}$$ chance that the algorithm fails, and otherwise $$gcd(s_{n, i}, s_{n, j})$$ is a non-trivial factor of $$n$$ that is a multiple of $$p$$. There is no worry even in case it failed, as we can start again with a different random seed.

Note that the algorithm will not stop if $$n$$ is prime, so we may need primality test algorithm such as Miller-Rabin to support Pollard’s algorithm.

ECFR #48 G