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.
Can anyone see what mistake I made?
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