素數檢測是密碼學、雜湊表、隨機數生成等領域的基礎操作。本文系統介紹從簡單試除法到概率性 Miller-Rabin 測試的完整演算法體系,提供 Python 高效實作與複雜度分析。
檢測 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
計算 aᵇ mod m,避免中間結果溢位。
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
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
費馬小定理:若 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
將 n-1 分解為 d × 2ˢ (d 為奇數)。若 n 為質數,對任意 a:
否則 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
需一次檢測大量數字或生成範圍內所有素數時:
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) |