判断正整数p是否是素数
方法一 朴素的判定
方法二 线筛
对于大整数(>1e9),可以优化
方法三 利用费马小定理
假如p是质数,且gcd(a,p)=1,那么 a^(p-1) ≡1(mod p)。
即:假如a是整数,p是质数,且a,p互质,那么a的(p-1)次方除以p的余数恒等于1。
我们这样写:a*a^(p-2) ≡1(mod p)
根据定义,a^(p-2)就是a (模p)的逆元
那么反过来,随机整数a能使p满足a^(p-1) ≡1(mod p)的话,那么p就是质数?
当然不是,虽然很大可能是,但是会有特殊的存在。
如2^340≡1(mod 341),但341=31*11
具体来说,特殊的数是费马伪素数和卡迈克尔数,这里不介绍了
方法四 二次探测定理
对于任意素数p, 满足方程![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAMUAAAAVBAMAAAAEKDfsAAAAMFBMVEX///8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMARFSZImYQMrvddqvNie8Nf0xcAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAC3UlEQVRIDbVUTUgUYRh+Znd+9sd2h6JDSTZYkAiVh5IoghEpIqodMGtFpKHoUBAOBREkbQhGeMkunjfCFL0sBdVFWCQIgij2kAcJ9ODdQLZLUe/3ffO5M+OsdfGD/d7ned5n3ne+n1mAjcRQF4/bOZ3H/HaW57VHUIzpoZdjRC41TTR7gOvfY7LZqGY8s4V0I5r5H65Phl3KR+IvwhqxNl9JOALsHTI3eZoKWS+UUqd/Eq+GNEbmpFLlwKjig1T+HafViId6yJcNZMYkrnGQsvBSKqorkYxnJRBRMTMMnHjKBpeoR8rmKDitS9LKQd7b2D3jjStzfnzY3RB2HtvdXfjzuyFwRD1ygDZ1c/B++zta09QiMNu+TGj2TB/Pka1ko+Rye2KcR+VAT58Q0PGKJYTbsB44zxkND+qRBnoeOYkFdAAncQkpJ1sBrg87SQd57t5PPWyGbo9yjrvGWNpkUJ+xuCLcGXoVh/PQRD0uANYAtAk6aa2KvFdEtgyYbdhRQc5lbmpAbYBeWikfZaOuMaCe8oQg3IHLgveh8xgh22lWdxw5B8PeKnLsyTlku5B2WY2Ch6MElBVG+MhUeGgzfS7cwILkwUjruEV8herq6yjYuKauo8Qco8hZ7Kxo5E0cYXFjHWixGG+sQ7gVtY4yT4Qm6kF11DUUaKNMKv7JWMOMQp469sgzTzn+F3PntXjYLLj8gkJfsoTC3QPapGYLHry7P4AWl51DEcmyk/a0Cpb1z7TZRh30H3AO6lvapMfyG9TGWQltYsC97NcqlhkQ7osH9x3y5UbQl34tImMh46AGpQa11g/sar93Bcgc77SBfhirZO88LDdemXdp2bWeGjsyPlq/URBuX4kJqji/SIb2h8YTuvrhRPx3LtxhZ4hRoc0jb5PG2kd6bHYyhbvjU0LtjUvyu5V06duJy0Y17o6KQa5YQSaw8uUrgav0s4Sw5SzcW1rsZtmmidgH/gIMvZoUzJQ+GwAAAABJRU5ErkJggg==)
有唯一解 x=1||p-1
证明
方法五 Miller Rabin算法
逆用费马小定理加上二次探测,就得到了 Miller Rabin 算法。
Miller Rabin 算法有一定的出错概率,出错的情况一定是将合数判定为素数,且出错概率极低
对于一个奇素数(偶素数只有2嘛),显然p-1是偶数
则有推导过程如下:
所以算法实现过程有两步:
1.枚举k,对于每一个k,检验是否满足二次探测定理(即上面的最后一步)
2.再检验
即
是否满足费马小定理![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAH8AAAAVBAMAAACd/CwcAAAAMFBMVEX///8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAdlQyIrtmq82J70QQmd0a05NiAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACAUlEQVQ4EZ1SP2jUUBz+cpdLNMn9qWJvEOF6IjjeYEFEaRZFFO0p6KLgE21d/HPQpeJSdXLyuA5yTp1c6nCbUFCCoLhoq0PBrZNzwRsEO/i95MXkJRGhGe59v+9f3r0XIP14R9LTLnDp6C5CWuSsNqnBaxSxkosF79B8P/IUFtjZfPmGH1GflWI5wUIEswXuU/IHlS1Z1hQsCQWmcc0YDocNZArM/T/pWFKuZGnGMJZu4nVEZQoAFvx9TZwCrsZwoMAjS53BRUlUr8inG2osqPghSv+M4+ENgbHvGH5MRYz78nYsqZUFDmBNfrxzsr3A3UwuAxPtFaKJM/dCjdtZ9LYysWRkQQ04f0KUnoBf2VecQ0XYPeD9uqgK1FnexUN3I0lkEAt4Lq37sLbQhLWEemcOdgMYrWFvD04AR2D1w3UtZutncJzidxm6JM3rnVdwOqSasDdQCzDrl7e1uD5wB1/IrDLkjWnGA3OMGem5DKclz2cGRnekh9ITC2gytzHL/Y+YfMz3HXBp2cG7UHPwqS/SEf0afwN7Avnf51BtiFrH6mHFe2YB5R3wKz0NuN8ObwZ6QTJ5L34tw2jBEBjAHcAczANv26fu8vY3p3yA4/8fs1fkqQjJ6qdf5Punq+5TKu7O9VzIMSTCm6gGRVKOc1s5Cu7zPslbeaGQ8QtZkhT+AOtwZG8D7+pXAAAAAElFTkSuQmCC)
对于任意一个p,如果通过了算法检验,则它不是素数的概率是25%
那么k轮之后,p不是素数的概率就是0.25^k,就很小了
一般8-10轮就差不多了
那么对于a的选择,可以选前面几个质数:2,3,5,7,11等,也可以用随机数
时间复杂度一般是
,k为测试的轮数
//里面有龟速乘和快速幂,防越界 inline int slow_mult(int a,int b,int mod){ int ans=0; while(b){ if(b&1) ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return ans; } inline int quick_pow(int a,int b,int mod){ int ans=1; while(b){ if(b&1) ans=slow_mult(ans,a,mod); a=slow_mult(a,a,mod); b>>=1; } return ans; } inline bool Miller_Rabin(int p){ if(p==2) return true; if(p==1||p%2==0) return false; int u=p-1,t=0; while(u%2==0) u/=2,t++; for(int i=0;i<=9;i++){//我测了十次 int a=rand()%(p-1)+1; int x=quick_pow(a,u,p); if(x==1) continue; for(int j=1;j<=t;j++){ int y=slow_mult(x,x,p); if(y==1 && x!=1 && x!=p-1) return false;//二次探测定理 x=y;//递推求2的幂 } if(x!=1) return false;//费马小定理 } return true; }