素数判定——Miller Rabin 算法

最近复习备战NOIP，开始回顾NOIP基础知识（才发现这么多不会= =b）

首先过关的是基础数论知识，从素数判定开始学起。

谈到素数判定，首先想到的两种便是暴力判定与筛法，实现非常简单，在此不提。

但在分解大质数时，由于数字过大，使得暴力判定会超时，筛法会超空间（可使用有技巧的限制空间筛法，但数字过大仍然过不了）

这时，我们就要引入非完美大质数判定算法——Miller Rabin算法。

下面一段引自sunshine_cfbsl博客：

这是一种随机性素数判定算法，也就是说，答案可能出错，但是可能性极小。

先是讲两个定理：

费马小定理： 对于一个质数p，取任意整数a，满足 gcd(p,a)=1 ，则有

ap−1≡1(mod p)

二次探测定理： 对于 0<x<p ，若p是素数，则方程：

x2≡1(mod p)

的解为：

x1=1,x2=p−1

因为费马小定理的逆命题不成立，而否逆命题成立，所以我们可以利用一下一点： 对于任意整数 a<p ，不满足 ap−1≡1(mod p) ，则p为合数。

所以我们可以不断在区间 [2,p−1] 范围内随机取a，并进行判定。在s次判定不为合数之后，我们就可以说这个数是质数。

但是这还不够精确，我们可以先把p−1分解成 2t×u(u为奇数) 的形式，然后令x[0]= aumodp ,，那么将x[0]平方t次就是 (au)2tmodp 的值，我们设x[i]为x[0]平方i次的值，根据二次探测定理，若x[i]等于1，则x[i−1]等于1或p-1，不满足则p为合数。

注意以上操作中所有的形如 abmodp 的式子都要用快速幂运算，当n比较大时，形如 a×bmodp 的式子也要使用分治的思想来计算。

这就是Miller-Rabin算法的主要内容。

时间复杂度：考虑常数后为 O(slog3n)

主要内容上面已经讲得很详尽了，要注意的是：

1、二次探测定理是为了提高Miller Rabin的准确性而额外增加的，在少数题中可以略去，但建议加上（不加的反例可能会在以后提到）

2、在实际操作中，可以略去数组，用双变量滚动赋值即可

3、快速幂与快速乘（只是这么叫而已。。。）的实现过程要简略而准确，以免出现不必要的失误

详见代码。

LL modmul(LL a,LL b,LL mod)//快速乘（又名：防爆乘法（瞎起的）） //与下快速幂原理类似，不赘述 { LL ret=0; for(;b;b>>=1,a=(a+a)%mod) if(b&1)ret=(ret+a)%mod; return ret; } LL qpow(LL x,LL u,LL mod)//快速幂，可以在对数复杂度内完成x^u计算 //分治思想，原理可以看网上博客 { LL ret=1LL; for(;u;u>>=1,x=modmul(x,x,mod)) if(u&1)ret=modmul(ret,x,mod); //可以参考的简洁快速幂写法，对位运算运用得也恰到好处 return ret; } bool Miller_Rabin(LL n)//n为待判断数 { LL x,pre,u=n-1;//pre用来记录x自乘之前的值，便于判断 int i,j,k=0; if(n==2||n==3||n==5||n==7||n==11)return 1; if(n==1||!(n%2)||!(n%3)||!(n%5)||!(n%7)||!(n%11))return 0; //节省时间（多此一举）的判断 while(!(u&1)) { k++; u>>=1; }//分解为上述形式 srand((long long)12234336); for(i=1;i<=50;i++) { x=rand()%(n-2)+2;//生成随机测试数 if(!(n%x))return 0; x=qpow(x,u,n);//先变为x^u形式，准备自乘 pre=x; for(j=1;j<=k;j++) { x=modmul(x,x,n);//x自乘 if(x==1&&pre!=1&&pre!=n-1)return 0;//二次探测 pre=x; } if(x!=1)return 0; } return 1; }

大素数判定算法到这里结束，其常与大数分解算法一起使用，在接下来的博客中会做介绍。