当你需要验证一个大数是否为素数时Miller-Rabin 算法就像一位经验丰富的侦探️‍♂️能在短时间内给出一个可靠的答案帮助你在数字的迷宫中找到真相。欢迎来到《密码学核心算法实战》的 Miller-Rabin 素数检验算法专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。Miller-Rabin算法的原理 Miller-Rabin算法基于两个数学定理费马小定理如果p pp是素数且a aa是一个整数满足1 a p − 1 1 a p-11ap−1那么a p − 1 ≡ 1 m o d p a^{p-1} \equiv 1 \mod pap−1≡1modp。二次剩余相关如果p pp是奇素数方程x 2 ≡ 1 m o d p x^2 \equiv 1 \mod px2≡1modp只有两个解x ≡ ± 1 m o d p x \equiv \pm 1 \mod px≡±1modp。首先将待检验的奇数n nn写成n − 1 2 s ⋅ d n-1 2^s \cdot dn−12s⋅d的形式其中d dd是奇数。然后使用费马小定理a n − 1 ≡ a 2 s ⋅ d ≡ ( … ( ( a d ) 2 ) 2 … ) 2 ≡ 1 m o d n a^{n-1} \equiv a^{2^s \cdot d} \equiv (\ldots ((a^d)^2)^2 \ldots)^2 \equiv 1 \mod nan−1≡a2s⋅d≡(…((ad)2)2…)2≡1modn如果n nn是素数最后的结果应该是1 11。然后从后往前看最后结果为1 11那么前一个结果要么是1 11要么是− 1 -1−1。所以如果n nn是素数那么在a d a^dad的平方过程中只有两个结果a d ≡ ± 1 m o d n a^d \equiv \pm 1 \mod nad≡±1modn平方后续全是1 11。a d ≢ 1 m o d n a^d \not \equiv 1 \mod nad≡1modn但在某次平方后变成− 1 -1−1之后的平方全是1 11。注意如果n nn是合数那么a d a^dad的平方过程中也可能出现1 11但前一个结果不是1 11或− 1 -1−1也就是在某次平方后出现1 11但前一个结果不是− 1 -1−1。我们将这个根叫做“非平凡平方根”如果存在非平凡平方根那么n nn一定是合数。综上所述如果n nn是素数那么a d a^dad的平方过程中只有两种情况要么一开始是± 1 \pm 1±1后面全是1 11要么在某次平方后出现− 1 -1−1之后全是1 11。如果出现了非平凡平方根那么n nn是合数如果啥也没有出现那么n nn很可能是合数。最后关于a aa的选择理论上来说随机选择a aa是可以的但为了保证算法的确定性我们可以选择一些特定的a aa例如在2 64 2^{64}264内的几个小素数这样就能保证对于2 64 2^{64}264内的数进行检验时算法是完全准确的。Miller-Rabin算法的操作 输入一个整数n nn以及一个整数k kk表示测试的轮数。输出一个布尔值表示n nn是否为素数。算法步骤如果n ≤ 1 n \leq 1n≤1返回 False如果n ≤ 3 n \leq 3n≤3返回 True如果n nn是偶数返回 False。将n − 1 n-1n−1写成2 s ⋅ d 2^s \cdot d2s⋅d的形式其中d dd是奇数。进行k kk轮测试选择一个整数a aa满足1 a n − 1 1 a n-11an−1。计算x a d m o d n x a^d \mod nxadmodn。如果x ≡ 1 m o d n x \equiv 1 \mod nx≡1modn或x ≡ n − 1 m o d n x \equiv n-1 \mod nx≡n−1modn继续下一轮测试。否则进行s − 1 s-1s−1次循环计算x x 2 m o d n x x^2 \mod nxx2modn。如果x ≡ n − 1 m o d n x \equiv n-1 \mod nx≡n−1modn跳出循环继续下一轮测试。如果循环结束后x ≢ n − 1 m o d n x \not\equiv n-1 \mod nx≡n−1modn返回 False。如果所有轮测试都通过返回 True。Miller-Rabin算法的实现 ‍️这个算法的实现非常简单核心就是根据上面的原理进行迭代检查。以下是一个Python实现defMiller_Rabin(n):# 特殊情况ifn1:returnFalseelifn3:returnTrueelifn%20:returnFalse# 把 n-1 写成 d * 2^sdn-1s0whiled%20:d//2s1# 对 2^64 内确定性测试a_list[2,3,5,7,11,13,17,19,23,29,31,37]foraina_list:xpow(a,d,n)# 计算 a^d mod nifx1orxn-1:# 如果 a^d ≡ 1 (mod n) 或 a^d ≡ -1 (mod n)继续测试下一个 acontinuefor_inrange(s-1):xpow(x,2,n)# 计算 x^2 mod nifxn-1:# 如果 x^2 ≡ -1 (mod n)继续测试下一个 abreakelse:returnFalsereturnTrueSageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimportis_prime# sage环境中才生效# 直接调用 is_prime 函数就可以了它内部已经部署了 Miller-Rabin 算法并且在此之上还做了很多优化能够快速准确地判断一个数是否为素数。flagis_prime(n)# flag 是一个布尔值True 表示 n 是素数False 表示 n 是合数怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋