Miller-Rabin 素性测试

定义

Miller-Rabin 素性测试是判断一个大整数是否为素数的概率算法,由 Gary Miller 于 1976 年提出确定性版本(依赖广义黎曼猜想),Michael Rabin 于 1980 年改造为无条件的随机化版本。

原理

将 n-1 写成 2^s·d(d 为奇数),随机取底数 a,用快速模幂计算 a^d mod n 及其连续平方。若结果序列不满足"首项为 1 或过程中出现 n-1",则 n 必为合数;否则 n 以高概率为素数。每轮误判(把合数判为素数)概率至多 1/4,k 轮独立测试后至多 (1/4)^k。单轮复杂度约 O(log³ n)。

应用

RSA 与 Diffie-Hellman 密钥生成中的大素数筛选、OpenSSL 与 GMP 等库的素性判定;对 64 位以内整数,选取固定的少量底数即可做到确定性正确。

对比

AKS 算法是确定性多项式时间,但常数太大,实践中仍以 Miller-Rabin 为主。