在现代密码学体系中，大整数素性判定是 RSA 公钥密钥生成、TLS 证书签发以及各类安全协议的核心基础设施。Miller-Rabin 概率素性测试自 1980 年由 Michael Oser Rabin 将 Gary Miller 的确定性方法转化为无条件的概率算法以来，始终是工业界实现素数生成的首选方案。与需要未证明数论假设的确定性版本相比，Miller-Rabin 只需要极少数的迭代次数即可将错误概率控制在密码学可接受的阈值之下。本文将从工程实现角度解析该算法的核心机制，并给出面向不同安全级别的参数配置建议。
算法核心机制与数学原理
Miller-Rabin 测试的数学基础建立在费马小定理的强化形式之上。给定待检测的奇整数 n（n > 2），首先将 n-1 分解为 2^s × d 的形式，其中 d 为奇数。随后，对于随机选取的底数 a（2 ≤ a ≤ n-2），算法执行以下判定序列：首先计算 x = a^d mod n；若 x 等于 1 或 n-1，则该底数通过测试，跳过剩余检测；否则，对 i 从 1 迭代到 s-1，计算 x = x^2 mod n，若 x 最终等于 n-1，则通过测试；若遍历完成后仍未命中 n-1，则 n 必定为合数。
这一判定逻辑之所以有效，源于强伪素数的数学性质。当 n 为素数时，上述序列必然在某个环节产生 n-1；而对于合数，大多数底数会在中途暴露其合成性质。关键在于，存在极少数被称为「强伪素数」的合数，它们对特定底数会表现出与素数完全相同的序列行为，这些底数被称为「强欺骗者」。Rabin 的核心贡献在于证明了对于任意奇合数 n，至少有四分之三的底数能够识别其为合数，这一无条件保证使得概率化方法具备了坚实的理论基础。
迭代次数与错误概率的量化关系
工程实现中，最关键的参数是迭代次数 k，即检测所采用的独立随机底数数量。根据算法理论，对于任意合数 n，单次测试的通过概率不超过四分之一；经过 k 次独立测试后，复合数被误判为素数的最大概率为 4 的负 k 次方。这一指数衰减特性使得错误概率能够通过少量迭代迅速降至密码学可忽略的程度。
具体而言，当 k = 8 时，最大错误概率为 4^-8 ≈ 1.5 × 10^-5；当 k = 16 时，错误概率降至约 4.3 × 10^-10；而 k = 32 时的错误概率已经降至 10^-19 量级。对于常规的 2048 位 RSA 密钥生成，大多数密码学库采用 8 到 12 次迭代，这在实际应用中已将错误概率压至远低于硬件故障概率的水平。对于需要更高安全保障的场景，如金融级密钥或长期签名密钥，可将迭代次数提升至 16 或 24 次，以获得更充裕的安全裕度。
实际工程中的参数选择策略
不同应用场景对错误概率的容忍度存在显著差异。在 TLS 证书签署场景中，一次性生成的素数若为合数将导致整个密钥对失效，但重复生成的成本相对可控，因此采用 8 次迭代配合后续的确定性验证是常见做法。OpenSSL 默认使用 12 次 Miller-Rabin 测试生成 1024 位素数，2048 位素数则使用 16 次迭代。OpenSSH 在生成 Diffie-Hellman 参数时同样依赖该测试，并通过额外的小素数除法检验进一步降低误判风险。
针对不同整数位宽，业界已形成相对成熟的迭代次数推荐。对于 512 位以下的短期场景，6 到 8 次迭代足以满足需求；1024 位密钥建议使用 12 次；2048 位及以上的长期安全需求则推荐 16 到 24 次。这一递进逻辑与密钥的安全生命周期相匹配：高强度密钥需要更可靠的素性保证，因为一旦泄露其影响持续时间更长、修复成本更高。
与 AI 安全推理的关联
在人工智能系统的安全推理层面，Miller-Rabin 测试体现了随机化算法在计算复杂性边界处的实用价值。AI 安全推理常常需要在不确定信息下进行快速决策，这与概率素性测试「以可控错误概率换取执行效率」的设计哲学高度相似。当推理系统需要在有限计算资源下对大量候选方案进行筛选时，类似 Miller-Rabin 的概率方法能够提供有效的工程折中。
特别是在大语言模型的密钥材料生成、联邦学习中的参数聚合验证、以及 AI 模型的知识产权保护等场景中，随机化算法为构建可信计算基座提供了关键技术支撑。理解 Miller-Rabin 的参数化逻辑，有助于工程师在 AI 安全系统的设计中做出更明智的工程权衡 —— 在安全性与效率之间寻找针对具体业务场景的最优平衡点。
资料来源：本文算法细节与参数建议参考 Miller–Rabin 素性测试的数学分析及相关密码学库的工程实践。