- Choose a number,
`N`, you wish to factor - Choose a number,
`a`, say`a`=`2` - Use division algorithm to see if
`a`is a factor of`N`- YES? - You found a factor, you are done
- NO? - Continue to step 4

- Calculate the order,
`r`, of the group <`a`> mod`N`- You can do this by looking at the sequence:
- [1,
`a`,`a`^2,`a`^3, ...] mod N

- [1,
- This sequence
`will`repeat. - The order,
`r`, is the length of one repitition.

- You can do this by looking at the sequence:
- Let
`t`=`a`^(`r`/2) mod`N` - Check to see if either
`t`+1 or`t`-1 are factors of`N`- YES? - You found a factor, you are done
- NO? - Choose the next
`a`, and go back to step 3

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

- Time Analysis: Too bad to even publish.
- Source Code: Check out the code
- 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