【算法】Miller_Rabin素数测试

用途：判断一个数是否是素数，为RSA公钥私钥 作基础


首先引入一下快速幂/积取模运算;

快速积取模:
原理：利用二进制减少运算的次数

1. #define  ll __int64
   
2. ll mulSpeed(ll a,ll b,ll n)
   
3. {
   
4.         ll s=0;
   
5.         while (b)
   
6.         {
   
7.                 if (b&1)
   
8.                 {
   
9.                         s=(s+a)%n;
   
10.                 }
    
11.                 a=(a+a)%n;
    
12.                 b>>=1LL;
    
13.         }
    
14.         return s;
    
15. }

复制代码

快速幂取模

1. ll powSpeed(ll a,ll b,ll n)
   
2. {
   
3.         ll s=1;
   
4.         while (b)
   
5.         {
   
6.                 if (b&1)
   
7.                 {
   
8.                         s=mulSpeed(s,a,n);
   
9.                 }
   
10.                 a=mulSpeed(a,a,n);
    
11.                 b>>=1LL;       
    
12.         }
    
13.         return s;
    
14. }

复制代码

费马小定理：
对于素数p和任意整数a 有a^p =a(mod p) 这里的等号是同余的意思，相反如果有a^p =a(mod p)，那么这个p一般来说是素数。

伪素数：
如果n是一个正整数，存在一个正整数a与n互素，满足 a^(n-1)=1(mod n),则n是基于a的一个伪素数，一般来说这个伪素数是素数。

Fermat素数测试：
循环s次，a是一个随机正整数，取值范围在[2,n-1]中，如果循环s次中，每一次都能满足a^(n-1)=1(mod n),那么这个数是素数，否则不是
注意：一个数如果不是素数，那么他一定不满足 2^(n-1)=1(mod n)
代码如下：
测试17是否是素数

1. int n=17,a=0,flag=1,s=10;    //在这里s=10
   
2.         srand((ll)time(0));
   
3.         for (int i=0;i<s;++i)
   
4.         {
   
5.                 a=rand()%(n-2)+2;
   
6.                 if (powSpeed(a,n-1,n)!=1)
   
7.                 {
   
8.                         flag=0;
   
9.                         break;
   
10.                 }
    
11.         }
    
12.         if (flag)
    
13.         {
    
14.                 printf("多半是素数\n");
    
15.         }
    
16.         else
    
17.         printf("不是素数");

复制代码

但是:Fermat素数测试是概率型的测试，成功率为3/4，如上面的例子也就是说17是否是素数的成功的概率是3/4。

为此引入二次探测定理

二次探测定理：
如果正整数p是奇素数（除了2的素数）x是小于p的正整数，且x^2==1(mod p) 那么x=1或x=p-1

证明：
相当于x^2-1整除p    (x+1)(x-1)整除p    x=1 x=-1 x=p-1 x=p+1 又因为x是小于p的正整数，所以
x=1 或x=p-1
证明完毕。

也就是说如果 x^2 %p==1,但是x!=1&&x!=p-1,这时候p就不是素数
举个例子：假设此时a=2,p=341 p-1=340可以分成  (2^170)^2  2^170可以分成(2^85)^2 ，直到拆不出2停止，这个时候这个计数是2，我们可以用二进制去计算这个计数，因为总是再分解2，2在二进制中是10，2^n在二进制中是1后面n个0,也就是说只要记录二进制从后往前有几个0，就知道有几个2，就知道是2的多少次方。
这样可以把这个数拆成 d*(2^k) 其中d是一个奇数（2都拆完了肯定是奇数）,k是有多少个2的次数

只要满足 x^2%x==1 而且x=1或x=p-1就行，还是341这个例子，我们来模拟一下他的步骤
假设此时a=2,p=341,p-1=340  有2^170,2^85

先算x  x=2^85%341  pre=x  把x先保存一份给pre 再算x^2   x^2=x*x%341  因为a*b%c=a%c*b%c
所以2^85%341*2^85%341=2^85*2^85%341
如果 x^2==1,就是满足 x^2%x==1  但是pre!=1&&pre=p-1 那么这个数字就不是素数
x=2^85%341=32   pre=x   x^2=2^85%341*2^85%341=1   此时x^2=1但是pre!=1或340 所以他不是素数
倘若 pre==1或pre==340  那么把x^2存一份给pre,此时的pre=2^170%341 继续循环判断

代码如下：

1. bool Miller_Rabin(ll n)
   
2. {
   
3.         if(n==2||n==3||n==5||n==7||n==11||n==13||n==17||n==19)
   
4.                 return true;
   
5.         if(n==1||!(n%2)||!(n%3)||!(n%5)||!(n%7)||!(n%11)||!(n%13)||!(n%17)||!(n%19))
   
6.                 return false;
   
7. 
   
8.         //如果n不满足 2^(n-1) %n==1,那么他一定不是素数
   
9.         if (powSpeed(2,n-1,n)!=1)
   
10.                 return false;
    
11.         ll u=n-1; //a^(n-1)%n 如果是1 ，极大可能是素数，否则不是素数
    
12.         ll k=0;//计算 二进制后面有多少个0，为了拆成  奇数×2^k
    
13.         while (!(u&1)) //为了拆成一个 2^k *d 其中d 是奇数,每次都可以提取一个2
    
14.         {
    
15.                 ++k;
    
16.                 u>>=1LL;
    
17.         }
    
18.          //进行s次FerMat探测 const int s =8
    
19.         //  a^(n-1)%n 是否是1
    
20.         const int s=10;
    
21.         ll a=0,pre=0;
    
22.         srand(time(0));
    
23.         for (int i=0;i<s;++i)
    
24.         {
    
25.                 a=rand()%(n-2)+2;//取[2,n-1]
    
26.                 if (!(a%n))
    
27.                         continue;//如果这个a随机出来能与a整除 取不到模为1了，继续循环
    
28.                 a=powSpeed(a,u,n);//先算出x
    
29.                 pre=a;//保存一份x
    
30.                 for (int j=0;j<k;++j)//循环上面算出的2的多少次方的k的次数
    
31.                 {
    
32.                         a=mulSpeed(a,a,n);//这里算的是x^2
    
33.                         if (a==1&&pre!=1&&pre!=n-1) //如果x^2 也就是满足 a^2=1(mod n) 但是x却不是1或p-1
    
34.                         {
    
35.                                 return false;
    
36.                         }
    
37.                         pre=a;//继续保存一份 继续循环
    
38.                 }
    
39.         }
    
40.         return true;
    
41. }

复制代码

注意：Miller-Rabin素性测试也是概率型的，随机取k个数进行测试，失误率大概是4^(-k)，但是这种成功率是可以让我们接受的，
而且这是目前测试素数最好的方法。

这有很大用处啊。5225就是流弊~

其实素数的定义我都还给老师了

好！很好！非常好

这是什么东东看来我的研究下

哈哈，学习下，好流弊啊

我数论学的少，不要骗我