Example when N is the product of one prime number and one non-prime number, N = 837

Let's say N = 837. Let's trace through this example:

1. Pick a random integer a, so that a < 837. Our code picked 802 in this example.
2. Compute g = gcd(a,N) = gcd(802,837) = 1:
   3. Since g = 1, we have to keep going!
   4. Find the period of f(x) = a^x (mod N) = 802^x (mod 837). This period is r = 30:
      5. r = 30 is even, so we keep going!
      6. a^r/2 = 802^30/2(mod 837) = 433 and 433 ≠ -1 (mod 837) = 836, so we keep going!
      7. We've found two factors of 837. They are gcd(a^r/2 + 1, N) = gcd(802^30/2 + 1837) = 31 and gcd(a^r/2 + 1, N) = gcd(802^30/2 - 1837) = 27.

Let's check our work: 31 * 27 = 837. We got it right! Note that since one number isn't prime, there are a variety of different pairs of numbers that factor 837. The algorithm will always produce a valid pair, but which pair depends on the sequence of random numbers that have been chosen, so the algorithm may show can generically different results.