Classical Primality and Factoring
The Pollard Rho Factoring Method
Pollard's rho method: cycle detection in a pseudorandom sequence, the birthday bound, and Brent's improvement.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0653
Pollard's rho method finds a factor in time proportional to the square root of that factor, using almost no memory. It is the standard method for factors of moderate size.
The idea
Iterate a pseudorandom map modulo the number. The sequence of values modulo an unknown prime factor cycles much sooner than the sequence modulo the number itself, and detecting that shorter cycle reveals the factor.
Cycle detection
| Method | Memory | Cost |
|---|---|---|
| Floyd — tortoise and hare | Constant | Three iterations per step |
| Brent | Constant | Fewer iterations; typically faster |
| Storing values | Large | Impractical for the sizes involved |
Pollard rho with cycle detection
- Iterate two pointersOne at single speed and one at double, or use Brent's powers-of-two schedule.
- Take a GCDOf the difference with the number being factored.
- Check the resultA non-trivial GCD is a factor.
- Handle failureA GCD equal to the number means the cycle coincided; restart with a different constant.
Batching the GCDs
Failure and restart
Cost and range
| Factor size | Feasibility |
|---|---|
| Up to about 12 digits | Fast |
| 12 to 20 digits | Feasible |
| Beyond | Use ECM instead |
Application
Rho is the workhorse for the small factors encountered in smoothness testing and in factoring ideal norms, where factors are expected to be small and the number of calls is large.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.5.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.