【算法】Miller_Rabin素数测试
本帖最后由 gmh5225 于 2015-1-2 09:21 编辑用途：判断一个数是否是素数，为RSA公钥私钥 作基础
首先引入一下快速幂/积取模运算;
快速积取模:
原理：利用二进制减少运算的次数#definell __int64
ll mulSpeed(ll a,ll b,ll n)
{
ll s=0;
while (b)
{
if (b&1)
{
s=(s+a)%n;
}
a=(a+a)%n;
b>>=1LL;
}
return s;
}
快速幂取模
ll powSpeed(ll a,ll b,ll n)
{
ll s=1;
while (b)
{
if (b&1)
{
s=mulSpeed(s,a,n);
}
a=mulSpeed(a,a,n);
b>>=1LL;
}
return s;
}
费马小定理：
对于素数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是一个随机正整数，取值范围在中，如果循环s次中，每一次都能满足a^(n-1)=1(mod n),那么这个数是素数，否则不是
注意：一个数如果不是素数，那么他一定不满足 2^(n-1)=1(mod n)
代码如下：
测试17是否是素数
int n=17,a=0,flag=1,s=10; //在这里s=10
srand((ll)time(0));
for (int i=0;i<s;++i)
{
a=rand()%(n-2)+2;
if (powSpeed(a,n-1,n)!=1)
{
flag=0;
break;
}
}
if (flag)
{
printf("多半是素数\n");
}
else
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)^22^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
先算xx=2^85%341pre=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 继续循环判断
代码如下：
bool Miller_Rabin(ll n)
{
if(n==2||n==3||n==5||n==7||n==11||n==13||n==17||n==19)
return true;
if(n==1||!(n%2)||!(n%3)||!(n%5)||!(n%7)||!(n%11)||!(n%13)||!(n%17)||!(n%19))
return false;
//如果n不满足 2^(n-1) %n==1,那么他一定不是素数
if (powSpeed(2,n-1,n)!=1)
return false;
ll u=n-1; //a^(n-1)%n 如果是1 ，极大可能是素数，否则不是素数
ll k=0;//计算 二进制后面有多少个0，为了拆成奇数×2^k
while (!(u&1)) //为了拆成一个 2^k *d 其中d 是奇数,每次都可以提取一个2
{
++k;
u>>=1LL;
}
//进行s次FerMat探测 const int s =8
//a^(n-1)%n 是否是1
const int s=10;
ll a=0,pre=0;
srand(time(0));
for (int i=0;i<s;++i)
{
a=rand()%(n-2)+2;//取
if (!(a%n))
continue;//如果这个a随机出来能与a整除 取不到模为1了，继续循环
a=powSpeed(a,u,n);//先算出x
pre=a;//保存一份x
for (int j=0;j<k;++j)//循环上面算出的2的多少次方的k的次数
{
a=mulSpeed(a,a,n);//这里算的是x^2
if (a==1&&pre!=1&&pre!=n-1) //如果x^2 也就是满足 a^2=1(mod n) 但是x却不是1或p-1
{
return false;
}
pre=a;//继续保存一份 继续循环
}
}
return true;
}
注意：Miller-Rabin素性测试也是概率型的，随机取k个数进行测试，失误率大概是4^(-k)，但是这种成功率是可以让我们接受的，
而且这是目前测试素数最好的方法。
这有很大用处啊。5225就是流弊~
其实素数的定义我都还给老师了
好！很好！非常好
这是什么东东看来我的研究下
哈哈，学习下，好流弊啊
我数论学的少，不要骗我
页:
[1]