BACKGROUND
Written by J.D. Dixon in 1981.

This is a modified version of Fermat's factoring method and works very well on parallel procesors, because each procesor can work on its own random rk (see below).

BIG IDEA
Remember Fermat's Method? We were looking for numbers, x and y, such that:
N = x^2 - y^2, or more usefully put,
x^2 = y^2 (mod N)
If so, there is a 50% chance that the gcd(x-y, n) is a divisor of n. So choose a random number r, square it (mod n), try to factor it to see if that number is a square. If so it's square root can be different from r. If so, you got two numbers whoose squares are congruent mod n. That's it!

The hard part is finding such a solution. The bulk of this method (as well as Fermat's) is hunting for such squares. This method basically uses linear algebra. How? Watch. Nothing up my sleeves...

METHOD
  1. Choose the number you wish to factor, N
  2. Choose a few random integers, rk (usually taken to be sqrt(N)+k for k=1, 2, 3, ...
  3. Try to completely factor each rk^2 (mod N) trivialy (up to some trivial divisor d)
  4. Express each rk in terms of its prime factorization, i.e.
    rk = p1^a1 * p2^a2 * ... * pj^aj (where j = euler_phi(d) )
  5. Create a j-dimensional vector with the exponents
  6. If each ai's are even (0 mod 2), then rk is a square, goto step 8
  7. If not, try to find a linear combination of each rk vector that will give you all even terms, i.e. Ax = 0 (mod 2). This can be solved using Gaussian Elimination, mod 2
  8. This will give you a solution to x^2 = y^2 (mod N)
  9. You now have a 50% chance that gcd(x^2-y^2, N) > 1. If not goto step 2

TECHNICAL ANALYSIS
I am told, when you have a solution to:
x^2 = y^2 (mod N)
you have a 50% chance that x - y has a non-trivial divisor with N.
Theoretical Runtime:
O( ? ) (Better that trivial division)

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