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