galois.pollard_rho¶

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\text{mod}n$. The default is 1. A requirement of the algorithm is that $c\notin \{0,-2\}$.

Returns

A non-trivial factor $m$ of $n$, if found. None if not found.

Raises

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

See also

factors, pollard_p1

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\text{mod}p$ where $p$ is an unknown small prime factor of $n$. This happens when $x_m\equiv x_{2m}(\text{mod}p)$. Because $p$ is unknown, this is accomplished by computing the sequence modulo $n$ and looking for $\text{gcd}(x_m-x_{2m},n)>1$.

References

• Section 3.2.2 from https://cacr.uwaterloo.ca/hac/about/chap3.pdf

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