710官方网站p也差不离肯定是素数,当且仅当r(p-1) = 0(mod M(p))

费马小定理:对于素数p和轻易整数a,有ap ≡
a(mod p)(同余)。反过来,满足ap ≡ a(mod
p),p也大致肯定是素数。

Mason素数

费马小定理:对于素数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是素数,否则为合数。

伪素数:假如n是2个正整数,假若存在和n互素的正整数a满意an-1 ≡ 1(mod
n),大家说n是基于a的伪素数。要是3个数是伪素数,那么它大概肯定是素数。

定义:

  • if m是三个正整数 and 2^m-1是八个素数 then m是素数
  • if m是三个正整数 and m是一个素数 then M(m)=2^m-1被誉为第m个Mason数
  • if p是二个素数 and M(p)是二个素数 then M(p)被叫作Mason素数
Function Miller-Rabin (n : longint) :boolean;
begin
    for i := 1 to s do
    begin
        a := random(n - 2) + 2;
        if mod_exp(a, n-1, n) <> 1 then return false;
    end;
    return true;
end;

Miller-Rabin测试:不断选拔不超越n-1的基b(s次),总括是或不是每一遍都有bn-1 ≡
1(mod n),若每回都创设则n是素数,不然为合数。 

Lucas-Lehmer判定法:判定二个梅森数是还是不是是梅森素数

设p是素数,第p个Mason数为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))

1回探测定理:借使n是多个素数,且0<x<p,则方程x^2%p=1的解为:x=1或
   x=p-1.

预计:设p是素数,M(p)为第p个Mason数,则算法复杂度为O(n^3)

 

Mason素数 – nefu 120

思路:R.1 = 4;R.k = (R.k-1 ^ 2 – 2) % Mp;

一经昂科雷.p-1 == 0,则是梅森素数,不然不是。
独特判断:p == 2,即Mp = 3是Mason素数。

#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;
}

710官方网站 1710官方网站 2

模板:

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;
}
  1 //Achen
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<cstdio>
  7 #include<vector>
  8 #include<queue>
  9 #include<cmath>
 10 #include<ctime>
 11 const int N=1e5+7;
 12 typedef long long LL;
 13 using namespace std;
 14 int T;
 15 LL x,p[N]; 
 16 
 17 template<typename T> void read(T &x) {
 18     T f=1; x=0; char ch=getchar();
 19     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
 20     if(ch=='-') f=-1,ch=getchar();
 21     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
 22 }
 23 
 24 LL ksc(LL a,LL b,LL mod) {
 25     LL base=a%mod,res=0;
 26     while(b) {
 27         if(b&1) res=(res+base)%mod;
 28         base=(base+base)%mod;
 29         b>>=1;
 30     } 
 31     return res;
 32 }
 33 
 34 LL ksm(LL a,LL b,LL mod) {
 35     LL base=a,res=1;
 36     while(b) {
 37         if(b&1) res=ksc(res,base,mod);
 38         base=ksc(base,base,mod);
 39         b>>=1;
 40     }
 41     return res;
 42 }
 43 
 44 int miller_rabin(LL n) {
 45     LL u=n-1;
 46     int k=0;
 47     if(n==2||n==3||n==5||n==7||n==11) return 1; 
 48     if(!(n%2)||!(n%3)||!(n%5)||!(n%7)||!(n%11)) return 0;
 49     while(!(u&1)) {
 50         u>>=1; k++;
 51     }
 52     for(int i=1;i<=20;i++) {
 53         LL x=rand()%(n-2)+2;
 54         LL tp=ksm(x,u,n);
 55         for(int j=1;j<=k;j++) {
 56             LL tpp=ksc(tp,tp,n);
 57             if(tpp==1&&tp!=1&&tp!=n-1) return 0;
 58             tp=tpp;
 59         }
 60         if(tp!=1) return 0;
 61     }
 62     return 1;
 63 } 
 64 
 65 LL gcd(LL a,LL b) {return (!b)?a:gcd(b,a%b);}
 66 
 67 LL pallord_rho(LL n,int c) {
 68     LL x=rand()%n,y=x;
 69     int k=2,i=1;
 70     for(;;) {
 71         i++;
 72         x=(ksc(x,x,n)+c)%n;
 73         LL tp=gcd((x-y+n)%n,n);
 74         if(tp>1&&tp<n) return tp;
 75         if(x==y) return n; 
 76         if(i==k) y=x,k+=k;
 77     }
 78 }
 79 
 80 void find(LL n) {
 81     if(miller_rabin(n)) {
 82         p[++p[0]]=n;
 83         return ;
 84     } 
 85     LL p=n;
 86     for(int c=13;;c++) {
 87         p=pallord_rho(n,c);
 88         if(p>1&&p<n) break;
 89     }
 90     find(p); find(n/p);
 91 }
 92 
 93 int main() {
 94     read(T);
 95     while(T--) {
 96         p[0]=0;
 97         read(x);
 98         if(x==1||miller_rabin(x)) puts("Prime");
 99         else {    
100             find(x);
101             LL ans=p[1];
102             for(int i=2;i<=p[0];i++) ans=min(ans,p[i]);  
103             printf("%lld\n",ans);
104         }
105     }
106     return 0;
107 }

Miller-rabin 素数测试:间接判断M(p)是或不是素数

View
Code

理论知识:

费马小定理: 对于素数p和私自整数a,有ap ≡ a(mod
p)(同余)。反过来,满意ap ≡ a(mod p),p也大约肯定是素数。

伪素数: 假如n是八个正整数,如若存在和n互素的正整数a满足 an-1 ≡
1(mod
n),大家说n是基于a的伪素数。假设2个数是伪素数,那么它大致肯定是素数。

Miller-Rabin测试: 不断接纳不超过n-1的基b(s次),总计是不是每一遍都有bn-1
≡ 1(mod n),若每趟都创设则n是素数,不然为合数。

还有三个定律,能增高米尔er测试的功效:

三次探测定理: 假设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;
}

 

 

 

相关文章