BACKGROUND
Developed by John M. Pollard in the late 70's. Improved upon by R.P.Brent.
BIG IDEA
One of the reasons for the success of this algorithm is the Birthday
problem from undergraduate probability: If you are looking for two
numbers with the same property, it is very likely (i.e. in a classroom of
students it is very likely that two with have the same birthday.)
This method generates "random" numbers, say x and y,
and eventualy finds two that are congruent (mod N). This means
that x-y = 0 (mod N) and thus
x-y divides N. Done!
Of course, there are "fast ways" to generate so called "random" numbers
(mod N). The easiest way is to keep iterating your number
using some irreducible polynomial (except x^2 - 2). The Brent method uses
x^2 - c, c != 2
For more details, see the code.
METHOD
- Choose a number, N, you wish to factor
- Pick two random numbers (mod N), x and y
- Is the difference, x-y is 0 (mod N)?
- YES - You found a factor, namely gcd(x-y,
N)
- NO - go back to step 2
TECHNICAL ANALYSIS
Of course, there are "good" ways to pick random numbers (mod
N) so that you have a pretty good chance that they don't
repeat. There is also a good way to keep track of all the various
x's and y's so that you can efficiently check any
new x with any previously generated y (through
multiplication). For more details, check the code.
- Theoretical Runtime:
- O( sqrt(p) )
- where p is the largest prime factor of N
LINKS
Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page
Paul Herman
pherman@frenchfries.net
Last Updated: May 23, 1997