## Problem

Extract an arbitrary non-trivial factor of a given integer \(n\).

## Prerequisite

## 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.