当前位置：首页 > news >正文

Miller Rabin学习笔记

news 来源：原创 2024/5/17 17:56:36

这真是个优美的东西qwq

$O(\sqrt{n})$ 判素数非常好写，但这样的复杂度不够优秀，而学会了Miller Rabin算法就可以用神奇的方法做到 $O(n^{1/4})$ 判断了qwq。

前置芝士

费马小定理：当 $p$ 为素数切 $\gcd(a,p)=1$ ，有 $a^{p-1}\equiv1$ $(\mod p)$ ，这是 $p$ 为素数的必要不充分条件。
二次探测定理：当 $p$ 为素数且 $x\in(0,p)$ ， $x^2\equiv1$ $(\mod p)$ ，则 $x = 1$ 或 $x = p - 1$ 。将1移到等式左边即可证明。

Miller Rabin

首先我们知道，除了 $2$ 以外的素数都是奇数，那么特判掉 $2$ ，其余素数 $- 1$ 都是偶数。

假设当前要判定的奇数 $p$ 为素数，那么由费马小定理可知，对于任意 $a\in(0,n)$ ， $a^{p-1}\equiv1$ $(\mod p)$ ，而 $p - 1$ 又可以分解成 $2^k\times t(t\mod2=1)$ 的形式，当 $k\neq0$ 时，根据二次探测定理，可以一步一步降幂： $a^{2^k\times t}\equiv1(\mod p)\Rightarrow a^{2^{k-1}\times t}\equiv1(\mod p)$ 或 $a^{2^{k-1}\times t}\equiv n-1(\mod p)$ ，当第一种情况时又可以重复上述过程，直到 $a^{2^x\times t}\equiv n-1(\mod p)$ 或 $a^t\equiv 1(\mod p)$ 。

于是Miller Rabin算法每次选取一个素数 $a$ 来对 $p$ 进行检验，若存在 $x$ 使得 $a^{2^x\times t}\equiv n-1(\mod p)$ 或 $a^t\equiv 1(\mod p)$ ，则称 $p$ 通过了当前素性测试。

~~我不会证明但~~一次素性测试错误率约为 $\frac{1}{4}$ ，这里的错误是指素数一定能通过测试，合数不一定不能通过测试。所以在竞赛中常用 $30$ 以内的所有质数进行测试，这样得出的结果错误的概率极低，可以认为是正确的。

Code

由于 $p$ 大约在 $10^{18}$ 级别才会用到Miller Rabin，所以乘法的时候会有爆long long问题，要用龟速乘。

const int qwq[]={0,2,3,5,7,11,13,17,19,23,29};
inline int mul(int x,int y,int mod){
	int res=0;
	for(;y;y>>=1){
		if(y&1) res=(res+x)%mod;
		x=(x<<1)%mod;
	}
	return res;
}
inline int ksm(int x,int y,int mod){
	int res=1;
	for(;y;y>>=1){
		if(y&1) res=mul(res,x,mod);
		x=mul(x,x,mod);
	}
	return res;
}
inline bool MR(){
	if(n==2) return 1;
	if(n<2||!(n&1)) return 0;//特判 
	int t=n-1,k=0;
	while(!(t&1)) ++k,t>>=1;
	ff(i,1,10){
		if(qwq[i]==n) return 1;
		int a=ksm(qwq[i],t,n),now=a;
		ff(j,0,k){
			if(j) now=mul(a,a,n);
			if(now==1&&a!=1&&a!=n-1) return 0;//不满足二次探测定理 
			a=now;
		}
		if(a!=1) return 0;//不满足费马小定理 
	}
	return 1;
}