Developed by John M. Pollard in the late 70's. Improved upon by R.P.Brent.
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.
  1. Choose a number, N, you wish to factor
  2. Pick two random numbers (mod N), x and y
  3. Is the difference, x-y is 0 (mod N)?

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


Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman

Last Updated: May 23, 1997