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\ \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\), 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\ \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
Last update: Apr 21, 2022