梅森素数 判定总结 - Lucas-Lehmer算法 & Miller-rabin算法
梅森素数
定义:
- if m是一个正整数 and 2^m-1是一个素数 then m是素数
- if m是一个正整数 and m是一个素数 then M(m)=2^m-1被称为第m个梅森数
- if p是一个素数 and M(p)是一个素数 then M(p)被称为梅森素数
Lucas-Lehmer判定法:判定一个梅森数是否是梅森素数
设p是素数,第p个梅森数为M(p)为2^p-1,r1 = 4,对于k >= 2
r(k) = r(k+1)^2-2(modM(p)), 0 <= r(k) <= M(p)
可以得到r(k)序列,则有M(p)是素数,当且仅当r(p-1) = 0(mod M(p))
推论:设p是素数,M(p)为第p个梅森数,则算法复杂度为O(n^3)
梅森素数 - nefu 120
思路:R.1 = 4;R.k = (R.k-1 ^ 2 - 2) % Mp;
如果R.p-1 == 0,则是梅森素数,否则不是。
特殊判断:p == 2,即Mp = 3是梅森素数。
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; typedef long long ll; ll multi(ll a, ll b, ll m) { ll ret = 0; while(b>0) { if(b&1) { ret = (ret+a)%m; } b >>= 1; a = (a<<1)%m; } return ret; } int main() { ll sum = 1, data[66], tmp; int n, p; data[1] = 4; cin >> n; while(n--) { sum = 1; cin >> p; sum <<= p; sum -= 1; for(int i = 2; i <= p-1; i++) { tmp = multi(data[i-1],data[i-1],sum); data[i] = (tmp-2)%sum; } if(p == 2) cout << "yes" << endl; else { if(data[p-1] == 0) cout << "yes" <<endl; else cout << "no" << endl; } } return 0; }
模板:
long long multi(long long a, long long b, long long m){//实现a * b % m的操作,用2 * 3 = 6模拟一下就懂了 long long ans = 0; while(b > 0){ if(b & 1) ans = (ans+a) % m; b >>= 1; a = (a<<1) % m; } return ans; } //判断是否是梅森素数 bool is_msPrime(int p){ long long r[70]; long long m = 1; m <<= p; m -=1;//求出Mp; r[1] = 4LL; if(p == 2) return true; for(int i = 2; i <= p-1; ++i) r[i] = (multi(r[i-1],r[i-1],m)-2) % m; if(r[p-1] == 0) return true; return false; }
Miller-rabin 素数测试:直接判断M(p)是不是素数
理论知识:
费马小定理: 对于素数p和任意整数a,有ap ≡ a(mod p)(同余)。反过来,满足ap ≡ a(mod p),p也几乎一定是素数。
伪素数: 如果n是一个正整数,如果存在和n互素的正整数a满足 an-1 ≡ 1(mod n),我们说n是基于a的伪素数。如果一个数是伪素数,那么它几乎肯定是素数。
Miller-Rabin测试: 不断选取不超过n-1的基b(s次),计算是否每次都有bn-1 ≡ 1(mod n),若每次都成立则n是素数,否则为合数。
还有一个定理,能提高Miller测试的效率:
二次探测定理: 如果p是奇素数,则 x2 ≡ 1(mod p)的解为 x = 1 || x = p - 1(mod p);
两个高效求解a*b%m a^b%m的方法
// a * b % n //例如: b = 1011101那么a * b mod n = (a * 1000000 mod n + a * 10000 mod n + a * 1000 mod n + a * 100 mod n + a * 1 mod n) mod n ll mod_mul(ll a, ll b, ll n) { ll res = 0; while(b) { if(b&1) res = (res + a) % n; a = (a + a) % n; b >>= 1; } return res; }
//a^b % n //同理 ll mod_exp(ll a, ll b, ll n) { ll res = 1; while(b) { if(b&1) res = mod_mul(res, a, n); a = mod_mul(a, a, n); b >>= 1; } return res; }
代码如下:
bool miller_rabin(ll n) { if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true; if(n == 1 || !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11)) return false; ll x, pre, u; int i, j, k = 0; u = n - 1; //要求x^u % n while(!(u&1)) { //如果u为偶数则u右移,用k记录移位数 k++; u >>= 1; } srand((ll)time(0)); for(i = 0; i < S; ++i) { //进行S次测试 x = rand()%(n-2) + 2; //在[2, n)中取随机数 if((x%n) == 0) continue; x = mod_exp(x, u, n); //先计算(x^u) % n, pre = x; for(j = 0; j < k; ++j) { //把移位减掉的量补上,并在这地方加上二次探测 x = mod_mul(x, x, n); if(x == 1 && pre != 1 && pre != n-1) return false; //二次探测定理,这里如果x = 1则pre 必须等于 1,或则 n-1否则可以判断不是素数 pre = x; } if(x != 1) return false; //费马小定理 } return true; }