counterorbit.org - Brent-Pollard Integer Factorization

Brent-Pollard Integer Factorization

The Brent-Pollard integer factorization method is one of the fastest prime factorization methods available for numbers of approximately 10 decimal digits and smaller. It remains usable for slightly larger numbers, particularly if you are patient.

This project contains implementations of the Brent-Pollard method in several languages. The first implementation is a simple Python reference implementation that mirrors Brent's paper as much as possible.

Downloads are available on the Files page.

This project is distributed under the GNU General Public License version 3.

Implementations

Each implementation exports a single function. The function accepts an integer n and returns a sequence containing the integer factors of n. The sequence will contain duplicate factors whenever the factor is present more than once. For example, the factorization of 4 will contain 2 twice. The sequence will contain a single n when n is prime.

Each implementation will signal an error when n is less than 1. The error is signaled in the usual manner for each language.

Python: brent_pollard.brent_pollard(n)
Haskell: BrentPollard.brentPollard :: Integer -> [Integer]

Brent-Pollard Method

Brent, Richard P. (1980), "An improved Monte Carlo factorization algorithm", BIT 20: 176–184

http://maths.anu.edu.au/~brent/pub/pub051.html

00:  y := x₀; r := 1; q := 1;

01:    repeat x := y;

02:      for i := 1 to r do y := f(y); k := 0;

03:      repeat ys := y;

04:        for i := 1 to min (m,r-k) do

05:          begin y := f(y); q := q×|x-y| mod N

06:          end;

07:        G := GCD(q,N); k := k+m

08:      until (k≥r) or (G>1); r := 2×r

09:    until G>1;

10:    if G=N then

11:      repeat ys := f(ys); G := GCD(|x-ys|,N)

12:      until G>1;

13:    if G=N then {failure} else {success}.

The paper's results were obtained with:

00:  x₀   := 0

01:  m    := 1

02:  c    := 3

03:  f(x) := (x² + c) mod N

These are the constants and function used in all of the implementations.

Additional Information

After ten digits elliptic curve methods^[1], like Lenstra's elliptic curve factorization, start to surpass the Brent-Pollard method. For numbers of 100 decimal digits and more the General Number Field Sieve is currently the fastest method available. These other methods are beyond the scope of this project.

Notes

Brent has also published material on elliptic curve methods. This paper demonstrates that the elliptic curve methods are faster than the Brent-Pollard method beyond ten decimal digits. See Section 8 "Optimal choice of parameters", Table 1 "log₁₀ W versus log₁₀ p for Algorithms 1–4" on page 9.
Brent, Richard P. (1986), "Some integer factorization algorithms using elliptic curves", Australian Computer Science Communications 8: 149-163

http://maths.anu.edu.au/~brent/pub/pub102.html