galois.pollard_rho(n: int, c: int = 1) int

Attempts to find a non-trivial factor of $$n$$ using cycle detection.

Parameters:
n: int

An odd composite integer $$n > 2$$ that is not a prime power.

c: int = 1

The constant offset in the function $$f(x) = x^2 + c\ \textrm{mod}\ n$$. The default is 1. A requirement of the algorithm is that $$c \not\in \{0, -2\}$$.

Returns:

A non-trivial factor $$m$$ of $$n$$.

Raises:

RuntimeError – If a non-trivial factor cannot be found.

Notes

Pollard’s $$\rho$$ algorithm seeks to find a non-trivial factor of $$n$$ by finding a cycle in a sequence of integers $$x_0, x_1, \dots$$ defined by $$x_i = f(x_{i-1}) = x_{i-1}^2 + 1\ \textrm{mod}\ p$$ where $$p$$ is an unknown small prime factor of $$n$$. This happens when $$x_{m} \equiv x_{2m}\ (\textrm{mod}\ p)$$. Because $$p$$ is unknown, this is accomplished by computing the sequence modulo $$n$$ and looking for $$\textrm{gcd}(x_m - x_{2m}, n) > 1$$.

References

Examples

Pollard’s $$\rho$$ is especially good at finding small factors.

In [1]: n = 503**7 * 10007 * 1000003

In [2]: galois.pollard_rho(n)
Out[2]: 503


It is also efficient for finding relatively small factors.

In [3]: n = 1182640843 * 1716279751

In [4]: galois.pollard_rho(n)
Out[4]: 1716279751