Miller_Rabin质数判断
我们朴素的质数判断算法是枚举小于等于$\sqrt{n}$的数，判断是否都不能整除n，这样的复杂度是$\sqrt{n}$，那么当n的数量级达到$10^{18}$的时候就不够优越了。这时候我们的Millar_Rabin算法就闪亮登场了。
我们的故事从费马小定理讲起，$a^{p-1}$≡1(mod p)，当p为质数的时候。
在费马小定理被证明出来的很长一段时间内，人们都认为费马小定理的逆定理是正确的，即如果$2^{p-1}$≡1(mod p)，那么就认为p是个质数，但其实341就是一个反例，这种我们成为强伪素数的数可以把这种判定方法轻松卡掉。
但是我们发现了这样一个事情，我们称为二次探测定理
如果$x^2≡1$(mod p)，那么也就是说$(x+1)(x-1)≡0$ (mod p)，又因为p是质数，所以$x+1$≡0(mod p)或者
$x-1$≡0(mod p)，所以x mod p=1或者 x mod p=-1
那么我们有了二次探测定理，我们再来看341这个数。
$2^{340}$%341 == 1
$2^{170}$%341 == 1
$2^{85}$%341 == 32
这时候就出现问题了，我们就把341这个伪质数揪出来了。
我们把质数的这个序列找出来发现一定是形如1,1…1,1,1,1,p-1这样子的，p-1之后可以为无序，我们设x要判断的数，d为x去掉所有2因子之后的结果。先判断$2^{d}$%x为多少，然后不断地把d*2，继续判断余数。
只有出现这两种情况时我们认为x是质数
1.序列全为1
2.序列出现了p-1
我们结合代码来讲如何判断1
2
3
4
5
6
7for (int i=1;i<=t;i++){
LL d=x-1;
while (!(d&1)) d>>=1;
LL s=ksm(q[i],d,x);
while (s!=1&&s!=x-1&&d!=x-1) d<<=1,s=mul(s,s,x);
if (s!=x-1&&!(d&1)) return 0;//如果找到的是p-1则没事，如果找到的是1，(根据二次探测定理，1前面一定全是1）那么必须全为1。
}
但是这样判断并不一定完全正确，所以我们需要将2(上文中的底数)换成别的数，一般来说在long long 范围内，2，3，7，61就都够用了。
这是模板题 LOJ 143
Pollard_Rho
为什么要把这两个放在一起讲呢，因为这两个算法的正确性都有那么一点瑕疵，可能算是某种相同点吧，而且Pollard_Rho中要用到Miller_Rabin。
先贴出模板题吧，求$\phi(n)$，n<=$10^{18}$
如果直接暴力，也是根号的。
那么我们随机一个数判断是否为n的因数，也不是很优，甚至劣于暴力。
作者对于Pollard_Rho的复杂度证明也不是很精通，这里就讲一讲做法。
每次有一个n，我们先用Miller_Rabin 判断他本身是不是质数，如果不是质数，我们先在0…n-1范围内随机一个种子seed，我们依靠这个seed来形成一个随机序列，假设这个随机序列的这一项为x，那么下一项为(x*x+seed)%n，我们每次判断这个随机序列的a,b两项做差，用这个差和n取gcd，然后进一步分解。
看代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25LL Nex(LL x,LL n){
return (mul(x,x,n)+seed)%n;//mul为慢速乘，防止乘的时候爆long long
}
void Pollard_Rho(LL n){
if (n==1) return;
if (Miller_Rubin(n)){//这里计算phi
m[n]++;//m是个map
if (m[n]==1) ans=ans*(n-1);
else ans=ans*n;
return;
}
while (1){
seed=rand()*rand()%(n-1);//先随机一个seed
LL a=rand()%(n-1),b=Nex(a,n);
while (a!=b){
LL kk=gcd(n,abs(a-b));
if (kk>1){
Pollard_Rho(kk);
Pollard_Rho(n/kk);
return;
}
a=Nex(a,n),b=Nex(Nex(b,n),n);//这里很关键，b每次都比a多走一步，如果形成环的话，b势必会追上a，这种判环的方法最为好写，是floyd这个人发明的，注意，不是我们所熟知的那个3方的floyd。
}
}
}
以上就是Pollard_Rho 的实现过程，希望对大家有所帮助，如果有写的不对或不好的地方，欢迎评论指正，谢谢。