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

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...

- Choose the number you wish to factor,
`N` - Choose a few random integers,
`rk`(usually taken to be sqrt(`N`)+`k`for`k`=1, 2, 3, ... - Try to completely factor each
`rk`^2 (mod`N`) trivialy (up to some trivial divisor`d`)- If not successful, go back to step 2.

- Express each rk in terms of its prime factorization, i.e.

`rk`=`p1^a1`*`p2^a2`* ... *`pj^aj`(where`j`= euler_phi(`d`) ) - Create a
`j`-dimensional vector with the exponents - If each
`ai`'s are even (0 mod 2), then`rk`is a square, goto step 8 - 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 - This will give you a solution to
`x`^2 =`y`^2 (mod`N`) - You now have a 50% chance that gcd(
`x`^2-`y`^2,`N`) > 1. If not goto step 2

- Theoretical Runtime:
- O( ? ) (Better that trivial division)

- Time Analysis: See the results
- Source Code: See how it works
- Alternate Description

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