numbers - 费马素数检验

Question

据我了解，对于所有卡迈克尔数，费马的素数检验都应该失败。这似乎可以很好地识别素数，但是我测试的所有卡迈克尔数都返回了高 k 值的“复合”，这是出乎意料的。

谁能看到我犯了什么错误？

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

标签： numbersprimesprimality-test