from Crypto.Util.number import inverse, GCD, isPrime, getPrime
How do they work? For each odd positive integern,a set $W(n)⊂\mathbb{Z}_n$ is defined such that the following properties hold:
Def
Framework:
Remark:
Fermat's theorem:
Idea:
Algorithm:
import random
def fermat_test(n, k):
for i in range(k):
a = random.randint(2, n-2)
#print(a)
if GCD(a, n)!=1: ##Remark this should return COMPOSITE (since you found a divisor !=1) but to show the flaw we did it this way
i-=1
continue
if pow(a, n-1, n) != 1:
return 'Composite'
return 'Probably prime'
print(fermat_test(2403, 12))
p = getPrime(512)
print(fermat_test(p, 100))
Composite Probably prime
Carmichael numbers pass the test yet they aren't prime:
print(f"561 is {fermat_test(561, 100)} but 561 % 3 = {561 % 3}")
print(f"41041 is {fermat_test(41041, 100)} but 41041 % 11 = {41041 % 11}")
561 is Probably prime but 561 % 3 = 0 41041 is Probably prime but 41041 % 11 = 0