Later improved by the big cheese... GAUSS!

The trick is to note the difference error,

- Choose a number,
`N`, you wish to factor - Is
`N`a perfect square?- YES? - You found two factors! Take sqrt() and bail.
- NO? - continue to next step

- Let
`r`= sqrt(`N`), the integer square root. - Compute
`e`=`r`^2 -`N`, sometimes called "the residue" - Let
`u`= 2`r`+ 1, and`v`= 1 - If
`e`is zero, then we found a factor - namely (`u`-`v`)/2. If not... - As long as e is negative, add
`u`to`e`, then increment`u`by two - As long as e is positive, subtract
`v`from`e`, then increment`v`by two - Go back to step 6

`N`is small ( < 10,000,000 ), or...- the factor(s) you are looking for are "close" to sqrt(
`N`)

- Theoretical Runtime:
- O( exp(# of digits in
`N`) ) ...i think...

- Time Analysis: See how well it works with certain numbers
- Source Code: Attempt this at home!
- 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