Example when N is prime, N = 7

Let's trace this through an example. Imagine N = 7. Therefore, its factors will be 7 and 1. Let's see what the algorithm does:

1. Pick a random integer a, so that a < 7. Our code picked a = 4 in this example.
2. Compute g = gcd(a,N) = gcd(4,7) = 1:
   3. Since g = 1 we have to keep going!
   4. Find the period of f(x) = a^x (mod N) = 4^x (mod 7). This period is r = 3:
      5. r = 3 is odd, so we go back to the beginning!

To go back to the beginning, you should do the following:

1. Pick a random integer a, so that a < 7. Our code picked a=0 in this example.
2. Compute g = gcd(a,N) = gcd(0,7) = 7:
   3. Since g = 7 isn't equal to one, we're done. Two factors of 7 are g = 7 and 7/7 = 1 (7 and 1).