Miller-Rabin 素数判定 与 Pollard Rho
今天打模拟赛的时候没想到 \(T1\) 要这鸟玩意，不会，赛后去学习了一下
参考文献：
warzone大佬
不知道叫什么的大佬
oi-wiki
\(sto\) \(ywc\)大佬 \(orz\)
\(Miller-Rabin\)
这个东西是干嘛的捏。
在一个较为快速的时间内判断一个数是不是质数。
首先我们有两个前置知识。
-
费马小定理：当 \(p\) 为质数时，\(a^{p-1}\equiv1(mod\ p)\)
-
二次探测定理：如果 \(p\) 是奇素数，那么如果有 \(x^2\equiv 1(mod\ p)\) ，如果解为 \(\pm 1\) ，那么 \(n\) 大概率为质数，否则 \(n\) 一定为合数。
而其实对于素数判定来说，我们还有费马素数判定。
即倘若 \(a^{p-1}\equiv 1(mod\ p)\) ，那么我们可以猜测很大概率 \(p\) 为质数，当然这也有误差，有一些合数是判不出来的，比如 \(561\) ，所以仅有费马素数判定是不够的，我们还得有其他东西来辅助判断。
而辅助的东西就是 \(Miller-Rabin\)
\(Miller-Rabin\) 需要将费马小定理和二次探测定理结合起来使用。
所以我们先要指导一下为什么二次探测定理是正确的。
二次探测定理证明：
\(x^2\equiv 1(mod\ p)\Rightarrow x^2-1\equiv 0(mod\ p)\Rightarrow (x+1)(x-1)\equiv 0(mod\ p)\)
也就是说 \((x+1)(x-1)\) 是 \(p\) 的倍数，因为 \(p\) 是质数，所以 \(p\%(x+1)\) 不可能为 \(0\) ，而 \(p\%(x-1)\) 不可能为 \(0\) ，所以 \((x+1)(x-1)\) 不可能为 \(p\) 的倍数，所以只有可能 \((x+1)(x-1)=0\)
所以 \(x=\pm 1=1\ or\ p-1\)
证毕。
\(Miller-Rabin\) 实现：
\(a\) 是一个任意底数
\(a^{p-1}\equiv 1(mod\ p)\)
而对于 \(p-1\) 如果 \(p\) 是质数，那么我们只需要对 \(2\) 进行特判以后，那么 \(p-1\) 一定是偶数。
而任意偶数一定可以表示成 \(u\times 2^r\)
\(a^{p-1}=(a^{u})^{2^r}\equiv 1(mod\ p)\)
我们将逐次进行分解枚举，第一次判断 \(a^u\) 第二次是 \(a^{2u}\) 第三次是 \(a^{4u}\) ，也就是外面那层 \(2^r\) 。
然后我们对于所有的这些都进行判定之后就可以了。
但是这样我们归根结底也只能大概率判断他是一个素数，而不能确定，所以我们需要使用多个底数，然后有一些说法。
一般来说使用 \(2\sim 37\) 的素数判定即可，这样可以正确检验出 \(n\le 10^{18}\) 的质数 。
单次判定时间复杂度为 \(O(k \log^2 n)\) ，\(k\) 为选择的底数的个数。
还有一些具体的细节在代码里给出：
点击查看代码
int prime[10+10]={2,3,5,7,11,233,331},tim=7;
LL ksm(LL x,LL y,LL MODD) {
LL ret=1;
while(y) {
if(y&1) ret=ret*x%MODD;
x=x*x%MODD;
y>>=1;
}
return ret;
}
LL mul(LL x,LL y,LL MODD) {
LL ret=0;
while(y) {
if(y&1) ret=(ret+x)%MODD;
x=(x+x)%MODD;
y>>=1;
}
return ret;
}
bool miller_rabin(LL a,LL n) {
LL s=n-1,r=0;
while(!(s&1)) {
s>>=1;
++r;
}
LL x=ksm(a,s,n);//先求出a^u
for(int i=0;i<r;++i) {//每次翻倍
LL tmp=mul(x,x,n);//太大的时候用龟速乘，如果不用的话时间复杂度降到 $O(klogn)$
if(x!=1&&x!=n-1&&tmp==1) return false;
//将上一个x，作为底，如果他的平方为1，且他自己不为1，就不符合二次探测
x=tmp;
}
return (x==1);//费马判定
}
bool check(int n) {
if(n==1) return false;//特判
for(int i=0;i<tim;++i) {
if(n==prime[i]) return true;//特判
if(!miller_rabin(prime[i],n)) {
return false;
}
}
return true;
}
\(Pollard\ Rho\)
咕咕咕