Example when N is the product of two prime numbers, N is larger, N = 2257

Let's say N = 2257. Let's trace through this example.

1. Pick a random integer a, so that a < 2257. Our code picked a = 1344 in this example.
2. Compute g = gcd(a,N) = gcd(1344,2257) = 1:
   3. Since g = 1, we have to keep going!
   4. Find the period of f(x) = a^x (mod N) = 1344^x (mod 2257). This period is r = 180:
      5. r is even, so we keep going!
      6. a^r/2 = 1344^180/2(mod 2257) = 1768 since; 1768 ≠ -1 (mod 2257) = 2256, we keep going!
         
      7. We've found two factors of 2257. They are gcd(a^r/2 + 1, N) = gcd(1344^180/2 + 12257) = 61 and gcd(a^r/2 + 1, N) = gcd(1344^180/2 - 12257) = 37.

Let's check our work: 61 * 37 = 2257. We got it right!