萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 素數檢測演算法全解析:試除法、費馬測試、Miller-Rabin 與優化實作

素數檢測是密碼學、雜湊表、隨機數生成等領域的基礎操作。本文系統介紹從簡單試除法到概率性 Miller-Rabin 測試的完整演算法體系,提供 Python 高效實作與複雜度分析。

1. 試除法 — 基礎確定性演算法

檢測 2 到 √n 的所有整數是否能整除 n。


def is_prime_trial(n: int) -> bool:
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    # 僅檢測奇數因子
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True
  • 時間複雜度:O(√n)
  • 適用:n < 10¹² 以內的單次檢測
  • 優化:預計算質數表 (埃氏篩) 僅試除質數,加速 ~2x

2. 模冪運算 — 大數運算基石

計算 aᵇ mod m,避免中間結果溢位。

遞迴平方法 (Right-to-Left Binary Exponentiation)


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

迭代平方法 (Left-to-Right, 更高效)


def mod_pow_iter(x: int, n: int, p: int) -> int:
    res = 1
    x %= p
    while n:
        if n & 1:
            res = (res * x) % p
        x = (x * x) % p
        n >>= 1
    return res
  • 時間複雜度:O(log n) 乘法模運算
  • Python 內建 `pow(x, n, p)` 為 C 實現,效能最佳,**生產環境直接使用內建**。

3. 費馬素性測試 — 概率性演算法

費馬小定理:若 p 為質數,對任意 1 ≤ a < p,aᵖ⁻¹ ≡ 1 (mod p)。

反面:若對某 a 不成立,p **一定** 為合數。若成立,p **可能** 為質數 (存在偽素數/Carmichael 數)。


def fermat_test(n: int, base: int = 2) -> bool:
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return pow(base, n - 1, n) == 1

# 多基數測試降低錯誤率
def fermat_test_multi(n: int, bases: list = [2, 3, 5, 7, 11]) -> bool:
    if n < 2: return False
    for a in bases:
        if a >= n: continue
        if pow(a, n - 1, n) != 1:
            return False
    return True
  • 錯誤率:單基數 ~ 合數通過機率;多基數指數級下降。
  • Carmichael 數 (如 561, 1105, 1729) 會通過所有與其互質基數的測試。

4. Miller-Rabin 測試 — 工業標準概率性演算法

將 n-1 分解為 d × 2ˢ (d 為奇數)。若 n 為質數,對任意 a:

  1. aᵈ ≡ 1 (mod n),或
  2. 存在 0 ≤ r < s,使得 aᵈ·²ʳ ≡ -1 (mod n)

否則 n 為合數。


import random

def is_witness(a: int, n: int) -> bool:
    """返回 True 表示 a 是 n 為合數的證人"""
    if n < 2: return True
    if n % 2 == 0: return n != 2
    
    # 分解 n-1 = d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return False  # 通過測試,非證人
    
    for _ in range(s - 1):
        x = (x * x) % n
        if x == n - 1:
            return False  # 通過測試
    return True  # 是證人,n 為合數

def miller_rabin(n: int, k: int = 10) -> bool:
    """Miller-Rabin 測試,k 輪隨機基數"""
    if n < 2: return False
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for p in small_primes:
        if n % p == 0:
            return n == p
    
    for _ in range(k):
        a = random.randrange(2, n - 1)
        if is_witness(a, n):
            return False
    return True

確定性變體 (小範圍)

對 n < 2⁶⁴,測試特定基數集合即為**確定性**判斷:


# n < 2^64 確定性基數集
DETERMINISTIC_BASES_64 = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]

def is_prime_64(n: int) -> bool:
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2; s += 1
    for a in DETERMINISTIC_BASES_64:
        if a % n == 0: continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1: break
        else:
            return False
    return True

5. 篩法批量生成素數

需一次檢測大量數字或生成範圍內所有素數時:


def sieve(limit: int) -> list:
    """埃氏篩,返回 limit 以內所有素數"""
    is_prime = bytearray(b'\x01') * (limit + 1)
    is_prime[0:2] = b'\x00\x00'
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i : limit+1 : i] = b'\x00' * ((limit - i*i)//i + 1)
    return [i for i, val in enumerate(is_prime) if val]

def segmented_sieve(low: int, high: int) -> list:
    """分段篩法,適用大範圍 (如 10¹² 到 10¹²+10⁶)"""
    # 先篩出 √high 以內素數
    # 再分段標記 [low, high]
    pass  # 實作略

效能對比與選擇建議

演算法類型適用範圍單次耗時 (10⁹ 級)
試除法確定性n < 10¹²~ms 級
費馬 (多基數)概率性快速篩選~μs 級
Miller-Rabin (k=10)概率性通用、密碼學~μs 級
確定性 MR (64-bit)確定性n < 2⁶⁴~μs 級
埃氏篩批量確定性生成範圍內所有素數O(n log log n)

實務建議

  • **密碼學用途** (RSA 金鑰生成):使用確定性 Miller-Rabin (64-bit) 或 k≥20 隨機基數。
  • **一般應用** (雜湊表大小、隨機採樣):`pow(2, n-1, n) == 1` 快速篩選 + 少量 MR 輪數。
  • **Python 內建優勢**:`pow(base, exp, mod)` 為高度優化 C 實現,永遠優於手寫模冪。
  • **大整數 (>2⁶⁴)**:考慮 `gmpy2.is_prime` (GMP 庫封裝),速度快數量級。
copyright © 萬盛學電腦網 all rights reserved