Python 質數檢測演算法總覽：試除法、費馬測試與 Miller-Rabin

從基礎試除法到機率性檢測，完整比較 Python 質數判定的三種主流演算法。

1. 試除法

時間複雜度 O(√n)

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

2. 費馬小定理測試

若 n 為質數，對任意 a < n，有 aⁿ⁻¹ ≡ 1 (mod n)。
偽質數會誤判為質數，但效率高。

def xn_mod_p(x, n, p):
    if n == 0: return 1
    res = xn_mod_p((x*x) % p, n >> 1, p)
    if n & 1: res = (res * x) % p
    return res

def fermat_test_prime(n):
    if n == 1: return False
    if n == 2: return True
    return xn_mod_p(2, n-1, n) == 1

3. Miller-Rabin 測試

將 n-1 分解為 d·2ʳ，檢測 aᵈ mod n 是否為 1 或 n-1，或中間平方過程出現 n-1。
錯誤率 ≤ 4⁻ᵏ（k 為測試輪數），廣泛用於密碼學。

def miller_rabin_witness(a, p):
    if p == 1: return False
    if p == 2: return True
    n = p - 1
    t = int(math.floor(math.log(n, 2)))
    u = 1
    while t > 0:
        u = n // (2**t)
        if n % (2**t) == 0 and u % 2 == 1:
            break
        t -= 1
    b1 = b2 = xn_mod_p2(a, u, p)
    for i in range(1, t + 1):
        b2 = (b1 * b1) % p
        if b2 == 1 and b1 != 1 and b1 != p - 1:
            return False
        b1 = b2
    return b1 == 1

def prime_test_miller_rabin(p, k):
    while k > 0:
        a = random.randint(1, p - 1)
        if not miller_rabin_witness(a, p):
            return False
        k -= 1
    return True

選擇建議

• 小數值（< 10⁶）：試除法
• 大數快速篩選：費馬測試
• 密碼學/高可靠度：Miller-Rabin (k≥10)