title: Fermat's primality test
body: <p>From my understanding, the fermat's primality test should fail for all carmichael numbers. This seems to identify prime numbers fine, but all the carmichael numbers that I tested returned 'composite' for high k values, which is unexpected.</p>
  <p>Can anyone see what mistake I made?</p>
  <pre><code>def mod_exp(x, y, N):
      if y == 0:
          return 1
      z = mod_exp(x, y//2, N)
      if y % 2 == 0:
          return z*z % N
      else:
          return x * z*z % N
  
  def fermat(N,k):
      isPrime = 'prime'
      for i in range(k):
          a = random.randint(1, N - 1)
          if mod_exp(a, N - 1, N) != 1:
              isPrime = 'composite'
      return isPrime
  </code></pre>