密码学算法 - Miller-Rabin 素数检验
当你需要验证一个大数是否为素数时，Miller-Rabin 算法就像一位经验丰富的侦探🕵️♂️，能在短时间内给出一个可靠的答案，帮助你在数字的迷宫中找到真相。
欢迎来到《密码学核心算法实战》的 Miller-Rabin 素数检验算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。
Miller-Rabin算法的原理 🌟
Miller-Rabin算法基于两个数学定理：
- 费马小定理：如果p pp是素数，且a aa是一个整数，满足1 < a < p − 1 1 < a < p-11<a<p−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−1=2s⋅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-11<a<n−1。
- 计算x = a d m o d n x = a^d \mod nx=admodn。
- 如果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 nx=x2modn。
- 如果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):# 特殊情况ifn<=1:returnFalseelifn<=3:returnTrueelifn%2==0:returnFalse# 把 n-1 写成 d * 2^sd=n-1s=0whiled%2==0:d//=2s+=1# 对 2^64 内确定性测试a_list=[2,3,5,7,11,13,17,19,23,29,31,37]foraina_list:x=pow(a,d,n)# 计算 a^d mod nifx==1orx==n-1:# 如果 a^d ≡ 1 (mod n) 或 a^d ≡ -1 (mod n)，继续测试下一个 acontinuefor_inrange(s-1):x=pow(x,2,n)# 计算 x^2 mod nifx==n-1:# 如果 x^2 ≡ -1 (mod n)，继续测试下一个 abreakelse:returnFalsereturnTrueSageMath 偷懒 🤓👆
有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：
fromsage.allimportis_prime# sage环境中才生效# 直接调用 is_prime 函数就可以了，它内部已经部署了 Miller-Rabin 算法，并且在此之上还做了很多优化，能够快速准确地判断一个数是否为素数。flag=is_prime(n)# flag 是一个布尔值，True 表示 n 是素数，False 表示 n 是合数怎么样，是不是非常简单？🤣👉🤡
我的个人blog：Alice and Bobの神秘小屋