@OceanEye7年前
08/7
16:03
0x00
Miller_Rabin 素数判定
为什么要写这个……因为我把它忘掉了
于是写篇文章复习复习……
0x01
基础知识:
费马小定理
\(a^{n-1} \equiv 1\pmod n\)伪素数
如果n是一个正整数,如果存在和n互素的正整数a满足 \( a^{n-1} \equiv 1\pmod n\),我们说n是基于a的伪素数。如果一个数是伪素数,那么它是素数的可能性很大
Miller-Rabin测试
不断选取不超过\(n-1\)的基\(b\)(\(s\)次),计算是否每次都有\( b^{n-1} \equiv 1\pmod n\),若每次都成立则n是素数,否则为合数。
快速幂
这是基础知识……
快速乘
快速乘是在模意义下的乘法
具体来说就是a*b%c超出限制的时候用的 , 用了位运算的技巧
代码如下
1 2 3 4 5 6 7 8 9 10 |
ll fast_mul(long long a,long long b,long long mod) { static ll ret; for(ret=0;b;b>>=1) { if(b&1) ret=(ret+a)%mod; a=(a<<1)%mod; } return ret; } |
0x02
上面有了伪素数的定义……那么我们可以用一些朴素的方法来验证素数
比如……我们随机几个数然后跑跑
1 2 3 4 5 6 7 8 9 10 |
bool test(long long i) { ll c; for(int k=1;k<=5;k++) { c=rand()%(i-2)+1; if(ksm(c,i-1,i)!=1) return false; } return true; }//false表示不是质数,true表示这是质数 |
大概每次筛正确的概率是 \( frac{3}{4} \)
0x03
然后讲一个不是那么的平凡的优化
因为 \( a^{n-1} \equiv 1\pmod n\)
所以 \( a^{\sqrt{n-1}^{2}} \equiv 1 \pmod n\) 或者 \(a^{\sqrt{n-1}^{2}} \equiv n-1\pmod n\)
如果使用的话可以提高该算法的效率
参考以下的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
int prime[700000],tot; bool isp[10000010]; int k; ll n; ll mod_mul(ll a,ll b,ll mod) { static ll ret; for(ret=0;b;b>>=1) { if(b&1) ret+=a; ret%=mod; a=(a<<1)%mod; } return ret; } ll ksm(ll a,ll b,ll mod) { ll ret; for(ret=1;b;b>>=1) { if(b&1) ret=mod_mul(a,ret,mod); a=mod_mul(a,a,mod); } return ret; } bool isprime(ll val) { static int s; s=0; static ll c,res; bool flag; for(res=val-1;!(res&1);res>>=1,s++); For(i,0,9) { if(p[i]>=val) return true; if((c=ksm(p[i],res,val))==1) continue; if(c==val-1) continue; flag=false; for(int j=s;j;--j) { c=fast_mul(c,c,val); if(c==val-1) { flag=true; break; } } if(!flag) return false; } return true; } |