上一篇我们建立了模运算与扩展欧几里得算法的基本框架。在此基础上本篇处理两个更高级的问题给定一个大的奇数 nn判断它是否为素数如果不是找出它的一个非平凡因子。这两个问题在复杂度上有着天壤之别——素数检测可以在多项式时间内完成而大整数分解在经典计算模型下至今没有多项式算法。正是这种不对称性构成了RSA等公钥密码体制的安全基础。一、费马小定理与伪素数费马小定理是素数检测的第一个理论工具。其陈述极为简洁若 pp 为素数aa 为任意不被 pp 整除的整数则有ap−1≡1(modp)ap−1≡1(modp)证明基于群论中的一个基本事实模 pp 的既约剩余系构成一个乘法群其阶为 p−1p−1而群中任意元素的阶整除群的阶故 ap−1≡1(modp)ap−1≡1(modp)。这一定理给出了素数的一个必要条件自然引出一个朴素判定方法对给定的奇数 nn选取基 aa2≤a≤n−22≤a≤n−2计算 an−1 mod nan−1modn。若结果不为 11则 nn 必为合数。若结果为 11则 nn 可能是素数——但只是“可能”。事实上存在合数 nn 满足 an−1≡1(modn)an−1≡1(modn)。称这样的 nn 为以 aa 为底的费马伪素数。例如2340≡1(mod341)2340≡1(mod341)但 34111×3134111×31 是合数。更麻烦的是Carmichael数——对任意与 nn 互质的 aa 均满足 an−1≡1(modn)an−1≡1(modn) 的合数。最小的Carmichael数是 5613×11×175613×11×17。Carmichael数有无穷多个这意味着单纯的费马测试永远无法以确定性的方式将Carmichael数与真素数区分开。二、Miller-Rabin测试的数学原理Miller-Rabin测试通过引入二次探测机制克服了Carmichael数的漏洞。其理论基础是模素数的平方根性质若 pp 为奇素数则同余方程 x2≡1(modp)x2≡1(modp) 仅有平凡解 x≡±1(modp)x≡±1(modp)。证明极为简洁。x2≡1(modp)x2≡1(modp) 等价于 p∣(x−1)(x1)p∣(x−1)(x1)。由于 pp 是素数pp 整除乘积则必整除其中至少一个因子故 x≡1x≡1 或 x≡−1(modp)x≡−1(modp)。基于此Miller-Rabin测试按如下方式处理奇数 nnn2n2。首先将 n−1n−1 写为 2s⋅d2s⋅d其中 dd 为奇数。选取基 a∈[2,n−2]a∈[2,n−2]计算序列ad mod n, a2d mod n, a4d mod n, …, a2sd mod nadmodn,a2dmodn,a4dmodn,…,a2sdmodn这一序列中每一项都是前一项的平方。若 nn 为素数则序列的最后一项 a2sdan−1≡1(modn)a2sdan−1≡1(modn)费马小定理。因此序列中必须存在某个位置从该位置开始全部为 11。设该位置前一项为 xx则 x2≡1(modn)x2≡1(modn)由模素数平方根性质知 x≡±1(modn)x≡±1(modn)。由此提炼出Miller-Rabin测试的判定规则若序列中第一项为 11或序列中某项为 n−1n−1即 −1 mod n−1modn则 nn 通过本轮测试称 nn 是以 aa 为底的强伪素数。若序列中某项为 11 但其前一项既非 11 也非 n−1n−1或 an−1≢1(modn)an−1≡1(modn)则 nn 必为合数aa 称为 nn 为合数的见证。三、错误概率分析Miller-Rabin测试的核心优势在于其可证明的低错误概率。可以证明如下定理若 nn 是奇合数则在 [2,n−2][2,n−2] 中至多有 (n−1)/4(n−1)/4 个基 aa 会使 nn 通过Miller-Rabin测试。换言之随机选取一个基合数被误判为素数的概率不超过 1/41/4。证明的思路如下。设 nn 为奇合数考虑所有与 nn 互质且使 nn 通过测试的基 aa 的集合。可以证明这个集合是模 nn 乘法群 (Z/nZ)∗(Z/nZ)∗ 的一个真子群。根据群论真子群的阶至多为原群阶的一半。当 nn 不是Carmichael数时(Z/nZ)∗(Z/nZ)∗ 的阶小于 n−1n−1进一步分析可将比例压至 1/41/4。独立地执行 kk 轮Miller-Rabin测试每轮随机选取不同的基 aa。若所有轮均通过则合数被误判为素数的概率不超过 (1/4)k(1/4)k。取 k40k40错误概率降至约 10−2410−24远低于硬件故障导致的误判率。在实际密码学应用中通常取 k40k40 到 6464 之间在效率和安全性之间取得平衡。值得指出的是对于特定范围内的整数确定性地使用少数几个基即可完全判定。例如若 n264n264仅需测试 a∈{2,3,5,7,11,13,17}a∈{2,3,5,7,11,13,17} 这七个基即可给出确定性的结果。这意味着在实际应用中Miller-Rabin对于64位以内的整数事实上是一个确定性算法。四、Pollard Rho分解算法当Miller-Rabin确认 nn 为合数后下一步是找到 nn 的一个非平凡因子。Pollard于1975年提出的Rho算法是解决这一问题的经典概率方法其核心思想巧妙地利用了伪随机序列的碰撞。设 nn 为合数pp 为 nn 的某个非平凡因子未知。算法在模 nn 的整数环上迭代一个多项式函数 f(x)(x21) mod nf(x)(x21)modn生成序列 x0,x1,x2,…x0,x1,x2,…。根据生日悖论在模 pp 的意义下该序列期望在 O(p)O(p) 步内发生碰撞即存在 i≠jij 使得 xi≡xj(modp)xi≡xj(modp)从而 p∣gcd(∣xi−xj∣,n)p∣gcd(∣xi−xj∣,n)。算法的巧妙之处在于我们并不知道 pp 的值但我们可以计算 gcd(∣xi−xj∣,n)gcd(∣xi−xj∣,n)。当碰撞在模 pp 意义下发生但在模 nn 意义下未发生时该GCD恰为 nn 的一个非平凡因子。为高效地检测碰撞Pollard引入了一个称为Floyd环检测的技巧。维护两个指针慢指针每次迭代一步x←f(x)x←f(x)快指针每次迭代两步y←f(f(y))y←f(f(y))。每一步计算 gcd(∣x−y∣,n)gcd(∣x−y∣,n)。若结果为 11继续迭代若结果为 nn算法失败可更换初始值或函数重试若结果为 (1,n)(1,n) 之间的整数则找到了 nn 的一个非平凡因子。期望运行时间是分析Pollard Rho算法的核心。在模 pp 意义下的伪随机序列根据生日悖论期望在 O(p)O(p) 步内发生碰撞。由于 p≤np≤nnn 至少有一个因子 ≤n≤n期望迭代步数为 O(n1/4)O(n1/4)。每次迭代需要计算一次GCD代价为 O(log2n)O(log2n)。总期望复杂度为 O(n1/4log2n)O(n1/4log2n)这是关于输入规模lognlogn 比特的指数时间——因此Pollard Rho并非多项式算法但对于中等大小的整数如数十位十进制数字依然高效。在实际分解RSA模数通常为数百位十进制数字时Pollard Rho仅作为子程序处理较小的因子更大的因子需借助二次筛法或数域筛法等更复杂的算法。五、素数检测与分解的实践应用素数检测和因子分解在密码学中扮演着截然相反的角色。素数检测用于生成密钥——RSA密钥生成过程中需要随机生成大的素数 pp 和 qq。实际做法是随机生成一个大的奇数用Miller-Rabin测试检验若非素数则加2继续尝试。得益于素数定理nn 附近素数的密度约为 1/lnn1/lnn期望在 O(logn)O(logn) 次尝试内找到素数。因子分解则用于攻击密钥——若能高效分解 NpqNpqRSA即被攻破。正因经典分解算法的复杂度随 NN 的位数指数增长RSA在密钥长度足够如2048位时被认为是安全的。量子计算领域的Shor算法能在多项式时间内完成整数分解这也是后量子密码学研究的核心驱动因素之一。六、总结与展望从Miller-Rabin的 O(klog3n)O(klog3n) 到Pollard Rho的 O(n1/4)O(n1/4)概率方法使得素数检测在工程上变得可行也使得中等大小的整数分解在有限时间内完成。Miller-Rabin展示了如何通过独立重复将单次错误概率从常数压缩到任意小Pollard Rho展示了如何利用伪随机的碰撞特性在指数空间中探测隐藏的结构。基于本篇的素数判定与分解算法下一篇将直接进入现代公钥密码的核心——RSA加密与数字签名的完整数学原理。我们将看到扩展欧几里得算法第31篇、Miller-Rabin测试本篇和大整数的模幂运算如何共同构成了RSA这一影响深远的密码体制。
【算法分析与设计】第32篇：素数检测与大整数分解的概率方法
上一篇我们建立了模运算与扩展欧几里得算法的基本框架。在此基础上本篇处理两个更高级的问题给定一个大的奇数 nn判断它是否为素数如果不是找出它的一个非平凡因子。这两个问题在复杂度上有着天壤之别——素数检测可以在多项式时间内完成而大整数分解在经典计算模型下至今没有多项式算法。正是这种不对称性构成了RSA等公钥密码体制的安全基础。一、费马小定理与伪素数费马小定理是素数检测的第一个理论工具。其陈述极为简洁若 pp 为素数aa 为任意不被 pp 整除的整数则有ap−1≡1(modp)ap−1≡1(modp)证明基于群论中的一个基本事实模 pp 的既约剩余系构成一个乘法群其阶为 p−1p−1而群中任意元素的阶整除群的阶故 ap−1≡1(modp)ap−1≡1(modp)。这一定理给出了素数的一个必要条件自然引出一个朴素判定方法对给定的奇数 nn选取基 aa2≤a≤n−22≤a≤n−2计算 an−1 mod nan−1modn。若结果不为 11则 nn 必为合数。若结果为 11则 nn 可能是素数——但只是“可能”。事实上存在合数 nn 满足 an−1≡1(modn)an−1≡1(modn)。称这样的 nn 为以 aa 为底的费马伪素数。例如2340≡1(mod341)2340≡1(mod341)但 34111×3134111×31 是合数。更麻烦的是Carmichael数——对任意与 nn 互质的 aa 均满足 an−1≡1(modn)an−1≡1(modn) 的合数。最小的Carmichael数是 5613×11×175613×11×17。Carmichael数有无穷多个这意味着单纯的费马测试永远无法以确定性的方式将Carmichael数与真素数区分开。二、Miller-Rabin测试的数学原理Miller-Rabin测试通过引入二次探测机制克服了Carmichael数的漏洞。其理论基础是模素数的平方根性质若 pp 为奇素数则同余方程 x2≡1(modp)x2≡1(modp) 仅有平凡解 x≡±1(modp)x≡±1(modp)。证明极为简洁。x2≡1(modp)x2≡1(modp) 等价于 p∣(x−1)(x1)p∣(x−1)(x1)。由于 pp 是素数pp 整除乘积则必整除其中至少一个因子故 x≡1x≡1 或 x≡−1(modp)x≡−1(modp)。基于此Miller-Rabin测试按如下方式处理奇数 nnn2n2。首先将 n−1n−1 写为 2s⋅d2s⋅d其中 dd 为奇数。选取基 a∈[2,n−2]a∈[2,n−2]计算序列ad mod n, a2d mod n, a4d mod n, …, a2sd mod nadmodn,a2dmodn,a4dmodn,…,a2sdmodn这一序列中每一项都是前一项的平方。若 nn 为素数则序列的最后一项 a2sdan−1≡1(modn)a2sdan−1≡1(modn)费马小定理。因此序列中必须存在某个位置从该位置开始全部为 11。设该位置前一项为 xx则 x2≡1(modn)x2≡1(modn)由模素数平方根性质知 x≡±1(modn)x≡±1(modn)。由此提炼出Miller-Rabin测试的判定规则若序列中第一项为 11或序列中某项为 n−1n−1即 −1 mod n−1modn则 nn 通过本轮测试称 nn 是以 aa 为底的强伪素数。若序列中某项为 11 但其前一项既非 11 也非 n−1n−1或 an−1≢1(modn)an−1≡1(modn)则 nn 必为合数aa 称为 nn 为合数的见证。三、错误概率分析Miller-Rabin测试的核心优势在于其可证明的低错误概率。可以证明如下定理若 nn 是奇合数则在 [2,n−2][2,n−2] 中至多有 (n−1)/4(n−1)/4 个基 aa 会使 nn 通过Miller-Rabin测试。换言之随机选取一个基合数被误判为素数的概率不超过 1/41/4。证明的思路如下。设 nn 为奇合数考虑所有与 nn 互质且使 nn 通过测试的基 aa 的集合。可以证明这个集合是模 nn 乘法群 (Z/nZ)∗(Z/nZ)∗ 的一个真子群。根据群论真子群的阶至多为原群阶的一半。当 nn 不是Carmichael数时(Z/nZ)∗(Z/nZ)∗ 的阶小于 n−1n−1进一步分析可将比例压至 1/41/4。独立地执行 kk 轮Miller-Rabin测试每轮随机选取不同的基 aa。若所有轮均通过则合数被误判为素数的概率不超过 (1/4)k(1/4)k。取 k40k40错误概率降至约 10−2410−24远低于硬件故障导致的误判率。在实际密码学应用中通常取 k40k40 到 6464 之间在效率和安全性之间取得平衡。值得指出的是对于特定范围内的整数确定性地使用少数几个基即可完全判定。例如若 n264n264仅需测试 a∈{2,3,5,7,11,13,17}a∈{2,3,5,7,11,13,17} 这七个基即可给出确定性的结果。这意味着在实际应用中Miller-Rabin对于64位以内的整数事实上是一个确定性算法。四、Pollard Rho分解算法当Miller-Rabin确认 nn 为合数后下一步是找到 nn 的一个非平凡因子。Pollard于1975年提出的Rho算法是解决这一问题的经典概率方法其核心思想巧妙地利用了伪随机序列的碰撞。设 nn 为合数pp 为 nn 的某个非平凡因子未知。算法在模 nn 的整数环上迭代一个多项式函数 f(x)(x21) mod nf(x)(x21)modn生成序列 x0,x1,x2,…x0,x1,x2,…。根据生日悖论在模 pp 的意义下该序列期望在 O(p)O(p) 步内发生碰撞即存在 i≠jij 使得 xi≡xj(modp)xi≡xj(modp)从而 p∣gcd(∣xi−xj∣,n)p∣gcd(∣xi−xj∣,n)。算法的巧妙之处在于我们并不知道 pp 的值但我们可以计算 gcd(∣xi−xj∣,n)gcd(∣xi−xj∣,n)。当碰撞在模 pp 意义下发生但在模 nn 意义下未发生时该GCD恰为 nn 的一个非平凡因子。为高效地检测碰撞Pollard引入了一个称为Floyd环检测的技巧。维护两个指针慢指针每次迭代一步x←f(x)x←f(x)快指针每次迭代两步y←f(f(y))y←f(f(y))。每一步计算 gcd(∣x−y∣,n)gcd(∣x−y∣,n)。若结果为 11继续迭代若结果为 nn算法失败可更换初始值或函数重试若结果为 (1,n)(1,n) 之间的整数则找到了 nn 的一个非平凡因子。期望运行时间是分析Pollard Rho算法的核心。在模 pp 意义下的伪随机序列根据生日悖论期望在 O(p)O(p) 步内发生碰撞。由于 p≤np≤nnn 至少有一个因子 ≤n≤n期望迭代步数为 O(n1/4)O(n1/4)。每次迭代需要计算一次GCD代价为 O(log2n)O(log2n)。总期望复杂度为 O(n1/4log2n)O(n1/4log2n)这是关于输入规模lognlogn 比特的指数时间——因此Pollard Rho并非多项式算法但对于中等大小的整数如数十位十进制数字依然高效。在实际分解RSA模数通常为数百位十进制数字时Pollard Rho仅作为子程序处理较小的因子更大的因子需借助二次筛法或数域筛法等更复杂的算法。五、素数检测与分解的实践应用素数检测和因子分解在密码学中扮演着截然相反的角色。素数检测用于生成密钥——RSA密钥生成过程中需要随机生成大的素数 pp 和 qq。实际做法是随机生成一个大的奇数用Miller-Rabin测试检验若非素数则加2继续尝试。得益于素数定理nn 附近素数的密度约为 1/lnn1/lnn期望在 O(logn)O(logn) 次尝试内找到素数。因子分解则用于攻击密钥——若能高效分解 NpqNpqRSA即被攻破。正因经典分解算法的复杂度随 NN 的位数指数增长RSA在密钥长度足够如2048位时被认为是安全的。量子计算领域的Shor算法能在多项式时间内完成整数分解这也是后量子密码学研究的核心驱动因素之一。六、总结与展望从Miller-Rabin的 O(klog3n)O(klog3n) 到Pollard Rho的 O(n1/4)O(n1/4)概率方法使得素数检测在工程上变得可行也使得中等大小的整数分解在有限时间内完成。Miller-Rabin展示了如何通过独立重复将单次错误概率从常数压缩到任意小Pollard Rho展示了如何利用伪随机的碰撞特性在指数空间中探测隐藏的结构。基于本篇的素数判定与分解算法下一篇将直接进入现代公钥密码的核心——RSA加密与数字签名的完整数学原理。我们将看到扩展欧几里得算法第31篇、Miller-Rabin测试本篇和大整数的模幂运算如何共同构成了RSA这一影响深远的密码体制。
