【Miller-Rabin随机判素数算法】

实用性介绍：████████████████████████████████

科学性证明：████████████████████████████████

·在运算中尝试使用quick-pow和quick-mul加速。但实际告诉我们，在多次判素数的情况下，使用quick-mul反而会减速，原因可能是原装%运算消耗了大量时间。(复判重复数T取在4以上，不然很危险)

·大米饼目前只能将它作为“黑盒代码”。

·检验步骤：

如果x是一个奇素数，将x−1表示成r*2^k的形式，r是奇数，a与x是互素的任何随机整数，那么a^k ≡ 1 mod x或者对某个k₁(0 ≤ k₁≤ k-1, k₁∈Z) 等式a^(2*k₁*r) ≡ −1 mod x 成立

对于每一次实验，随机取检验算子a，带入定理2进行检验，看看在算子a下，n能否满足

a^r ≡ 1 mod x或者对某个j (0 ≤ k≤ s−1, k∈Z) 等式a^(2kr) ≡ −1 mod x

 1 #include<bits/stdc++.h>
 2 #define go(i,a,b) for(int i=a;i<=b;i++)
 3 #define T 5
 4 #define ll long long 
 5 using namespace std;int n;
 6 ll Mul(ll a,ll b,ll mod){ll R=0;while(b)b&1?b--,R=(R+a)%mod:1,b/=2,a=(a+a)%mod;return R;}
 7 ll Pow(ll a,ll b,ll mod){ll R=1;while(b)b&1?R=Mul(R,a,mod):1,b/=2,a=Mul(a,a,mod);return R;}
 8 bool witness(ll x,ll a)
 9 {
10     ll r=x-1,k=0,t;while(!(r%2))r/=2,k++;
11     if((t=Pow(a,r,x))==x-1||t==1)return 1;
12     while(k--){t=Mul(t,t,x);if(t==x-1)return 1;}return 0;
13 }
14 bool Miller_Rabin(int x)
15 {
16     if(x==2)return 1;if(x<2||x%2==0)return 0;go(i,1,T)
17     {ll a=1ll*rand()%(x-1-1+1)+1;if(!witness(x,a))return 0;}return 1;
18 }
19 int main()
20 {
21     srand(time(NULL));
22     while(~scanf("%d",&n))
23     {
24         if(Miller_Rabin(n))printf("是的是的，是素数。
");
25         else printf("很遗憾,它不是素数(这有什么值得遗憾的呢？)
");
26     }
27     return 0;
28 }//Paul_Guderian

Try everything to make the world a better place!————Juddy·Hopps