当前位置:网站首页>Prime number determined by Miller Rabin

Prime number determined by Miller Rabin

2020-11-17 14:57:06 *LZX*

The purpose of the article : Determine whether a large number is a prime

Preposition theorem :1. all >2 All primes can be uniquely expressed as the difference between two squares p=a^2-b^2

therefore p=(a+b)(a-b) because p Prime number therefore a+b=p,a-b=1;

2. Fermat's small Theorem a^(p-1)≡1(mod p) (gcd(a,p)=1;)

On the subject : We according to the a^(p-1)≡1(mod p) We can get an inverse proposition ( false ) When a<p If you are satisfied a^(p-1)mod p=1, that p It's a prime number , But I found it was fake by typing the watch .

But only a small number of combinations satisfy this condition , So we can think of , use a=2~m To exclude one by one , Satisfy a^(p-1)mod p=1 Is not necessarily a prime number , But what's unsatisfied must not be , Just one of them a If you are not satisfied, it must not be

But, Some disgusting primes are still satisfied , So we can use a new theorem If p Prime number ,x Less than p The positive integer , And x^2 mod p = 1, or x=1, or x=p-1, Proof and prepositional Theorem 1 Almost x^2-1=py, py=(x+1)(x-1); namely p aliquot (x+1)(x-1) therefore ......

Then we can combine Fermat's small theorem with the above theorem : take p-1 Decompose into p-1=d*(2^r), Constantly to d Do the square operation , If the nontrivial square root is found, it can be judged that it is not a prime number . for example 2^340 mod 341=1---> 2^170 mod 341=1--->2^85 mod 341==32 therefore 341 Not primes

summary

Constantly extracting the index p-1 The factor in 2, hold p-1 Expressed as d2^r( among d It's an odd number ). So what we need to calculate becomes a Of d2^r The power divided by n The remainder of . therefore ,a^(d 2^(r-1)) Or equal to 1, Or equal to n-1. If a^(d 2^(r-1)) be equal to 1, The theorem continues to apply to a^(d 2^(r-2)), It's going to go on like this , Until for someone i Satisfy a^(d 2^i) mod n = n-1 Or... In the final index 2 Use up what you get a^d mod n=1 or n-1. So you OK 了 , But the accuracy is still not 100%, But it's also very high , Suggest using 8 Time a To judge

This konjaku finished , If there is any mistake, please advise me

Reference text (https://oi-wiki.org/math/prime/) (http://www.matrix67.com/blog/archives/234)

inline ll ksc(ull x,ull y,ll p){//O(1) Fast ride ( Explosion proof long long)
    return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}

inline ll ksm(ll x,ll y,ll p){// Fast power 
    ll res=1;
    while(y){
        if(y&1)res=ksc(res,x,p);
        x=ksc(x,x,p); y>>=1;
    }return res;
}

inline bool mr(ll x,ll p){
    if(ksm(x,p-1,p)!=1)return 0;// Fermat's small Theorem 
    ll y=p-1,z;
    while(!(y&1)){// It has to be squared 
        y>>=1; z=ksm(x,y,p);// Calculation 
        if(z!=1&&z!=p-1)return 0;// Not prime 
        if(z==p-1)return 1;// It must be for 1, To continue the second probe // namely p aliquot (x+1)(x-1)
    }return 1;
}

inline bool prime(ll x){ if(x<2)return 0;
    if(x==2||x==3||x==5||x==7||x==43) return 1;// You can do it yourself 
    return mr(2,x)&&mr(3,x)&&mr(5,x)&&mr(7,x)&&mr(43,x);
}

 

版权声明
本文为[*LZX*]所创,转载请带上原文链接,感谢

随机推荐