Miller-Rabin素性测试
先挂个m67的博客保平安 众所周知,我们可以在(O(sqrt{n}))的时间能准确判断一个数是否为质数,但是在很多情境下我们需要快速判断一个(10^{18})级别的数是否为质数,这个时候朴素的做法就行不通了 这个时候就需要使用(rm Miller-Rabin)了 主要用到两个定理
现在对于一个待检测的数(n),我们先搞一个比它小的底数(a),先求一下(a^{n-1}(mod n))的值,如果不等于1,我们可以断定这个数不是质数。但是当(a^{n-1}equiv 1(mod n))的时候,由于费马小定理的逆命题并不成立,所以我们无法断言(n)就是一个素数 这个时候就需要用到二次探测了,由于(a^{n-1}equiv 1(mod n)),如果(n)为素数,(a^{frac{n-1}{2}}equiv 1)或(n-1);如果(frac{n-1}{2})是个偶数并且(a^{frac{n-1}{2}}equiv 1(mod n)),那么我们使得(n=frac{n-1}{4})继续进行二次探测;如果(frac{n-1}{2})是个奇数或(a^{frac{n-1}{2}}equiv n-1(mod n)),我们就不能继续探测,可以暂时认为(n)是一个素数 选择一个底数可能并不能准确判断,于是多选几个底数试试即可 抄的慎老师的板子 const int mb[]={2,3,5,7,61,709,2003}; inline LL mul(LL a,LL b,LL P) { LL S=0;if(b>a) std::swap(a,b); for(;b;b>>=1ll,a=(a+a)%P) if(b&1ll) S=(S+a)%P; return S; } inline LL ksm(LL a,LL P) { LL S=1; for(;b;b>>=1ll,a=mul(a,a,P)) if(b&1ll) S=mul(S,P); return S; } int chk(LL x,LL p,LL y) { LL t=ksm(x,y,p); if(t!=1&&t!=p-1) return 0; if(t==p-1) return 1; if(t==1&&(y%2)) return 1; return chk(x,p,y>>1ll); } inline int mr(LL n) { if(n<=1) return 0; for(re int i=0;i<7;++i) if(n==mb[i]) return 1; for(re int i=0;i<7;++i) if(!chk(mb[i],n,n-1)) return 0; return 1; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |