米勒 - 拉宾素性检验

背景与历史发展

素数判定是数论中的核心问题，传统试除法因时间复杂度为 而无法处理大整数。1976 年，卡内基梅隆大学的 Gary Lee Miller 基于广义黎曼猜想提出了一种确定性素性检验算法，但由于该假设尚未被证明，1980 年 Michael O. Rabin 将其改进为随机化算法，形成了如今广泛应用的米勒 - 拉宾素性检验 。该算法在密码学（如 RSA 密钥生成）和计算机科学中具有重要地位，其时间复杂度为 ，其中 为测试轮数，显著优于试除法 。

尽管 2002 年 Agrawal 等人提出了确定性多项式时间算法 AKS，但米勒 - 拉宾因其高效性和易于实现，仍是实际应用中的首选。其核心创新在于结合费马小定理与二次探测定理，有效解决了费马测试中卡迈克尔数导致的误判问题。

数学基础与定义

核心定理

费马小定理：若 是素数， 是与 互素的整数，则 。该定理给出了素数的必要条件，但逆命题不成立，例如卡迈克尔数 满足对所有 与 561 互素时 。

二次探测定理：若 是素数，且 ，则 或 。证明如下：
，由于 是素数，故 或 ，即 。

算法定义

对于奇整数 ，将 分解为 （其中 为奇数）。若存在 （称为基），使得：

1. ，或
2. 存在 使得 ，
   则 可能是素数；否则 必为合数。满足上述条件的合数称为强伪素数（以 为基）。

详细推导过程

算法正确性证明

必要性：若 是素数，则对任意 与 互素，由费马小定理知 。考虑序列 。若 ，则条件 1 满足；否则，存在最小 使得 ，此时 ，由二次探测定理得 ，即条件 2 满足 。

充分性（概率保证）：对合数 ，能通过基 测试的概率不超过 。证明如下：
设 是合数且通过基 的测试，则 或存在 使得 。若 有非平凡因子分解 ，则 在模 和模 下的阶需满足特定条件，导致可选 的比例受限。通过 次独立测试，误判概率降至 。

算法步骤推导

1. 预处理：若 ，返回合数；若 ，返回素数；若 为偶数，返回合数 。
2. 分解 ：将 表示为 ，其中 为奇数。例如， 时， ，故 。
3. 随机选择基 ：从 中选取随机数 。对特定范围可使用固定基（如 64 位整数用 ）。
4. 计算 ：若 或 ，通过测试；否则进入循环 。
5. 二次探测循环：对 到 ，计算 。若 ，通过测试；若 ，未通过（因前一步 ）；循环结束后若 ，未通过 。

使用方法与实例

算法流程

以 （合数）和 为例：

1. ，故 。
2. 计算 。
3. 循环 ： ； ： 。
4. 最终 ，故 为合数 。

以 （素数）和 为例：

1. ， 。
2. 。
3. ： ，通过测试 。

确定性与优化

• 确定性测试：对 ，使用固定基集合可确保无误判 。
• 模幂优化：采用 Montgomery 模乘算法或快速幂（二进制 exponentiation）降低时间复杂度 。
• 错误概率控制：进行 轮测试，误判概率为 ，实际应用中 即可满足安全需求 。

应用与扩展

米勒 - 拉宾算法在密码学中用于生成大素数（如 RSA 密钥），其高效性使其成为主流选择 。此外，结合 Lucas 序列的混合测试可进一步降低误判率 。理论上，若扩展黎曼假设成立，米勒检验可转化为确定性算法，但其复杂度高于随机化版本 。

尽管 AKS 算法是确定性多项式时间算法，但米勒 - 拉宾在实践中仍不可替代，尤其在处理 以上大整数时，其 复杂度显著优于 AKS 的 。未来随着量子计算发展，该算法在抗量子密码学中的角色值得进一步研究。

米勒 - 拉宾素性检验的成功，体现了随机化算法在解决经典数论问题中的深刻价值，以可控的概率误差换取计算效率的飞跃，这一思想也启发了密码学、算法设计等多个领域的创新。