## Search This Blog

- Pick a random number
*a* < *N* - Compute gcd(
*a*, *N*). This may be done using the Euclidean algorithm. - If gcd(
*a*, *N*) ≠ 1, then there is a nontrivial factor of *N*, so we are done. - Otherwise, use the period-finding subroutine (below) to find
*r*, the period of the following function: - ,

i.e. the smallest integer *r* for which *f*(*x* + *r*) = *f*(*x*). - If
*r* is odd, go back to step 1. - If
*a* ^{r/2} ≡ -1 (mod *N*), go back to step 1. - The factors of
*N* are gcd(a^{r/2} ± 1, *N*). We are done.

Post a Comment