MR素性检测算法
转载地址： http://m.blog.csdn.net/blog/spirtsong/38273187
素数是除了自身和1以外，没有其它素数因子的自然数。自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。
鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找质数公式，到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。 素性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者则反之。
这里主要讲米勒拉宾算法，最后提供c++实现代码。
要测试 是否为素数，首先将 分解为 。在每次测试开始时，先随机选一个 介于 的整数 ，之后如果对所有的 ，若 且 ，则 N 是合数。否则， 有 的概率为素数。
Miller- Rabin算法随机生成底数a，进行多次调用函数进行测试，Miller-Rabin检测也存在伪素数的问题，但是与费马检测不同，MR检测的正确概率不 依赖被检测数p，而仅依赖于检测次数。已经证明，如果一个数p为合数，那么Miller-Rabin检测的证据数量不少于比其小的正整数的3/4，换言 之，k次检测后得到错误结果的概率为(1/4)^k。我们在实际应用中一般可以测试15~20次。
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 long long qpow(int a,int b,int r)//快速幂 6 { 7 long long ans=1,buff=a; 8 while(b) 9 {10 if(b&1)ans=(ans*buff)%r;11 buff=(buff*buff)%r;12 b>>=1;13 }14 return ans;15 }16 bool Miller_Rabbin(int n,int a)//米勒拉宾素数测试17 {18 int r=0,s=n-1,j;19 if(!(n%a))20 return false;21 while(!(s&1)){22 s>>=1;23 r++;24 }25 long long k=qpow(a,s,n);26 if(k==1)27 return true;28 for(j=0;j<r;j++,k=k*k%n)29 if(k==n-1)30 return true;31 return false;32 }33 bool IsPrime(int n)//判断是否是素数34 {35 int tab[]={2,3,5,7};36 for(int i=0;i<4;i++)37 {38 if(n==tab[i])39 return true;40 if(!Miller_Rabbin(n,tab[i]))41 return false;42 }43 return true;44 }45 int main()46 {47 long long n;48 while(1)49 {50 cin >> n;51 cout << IsPrime(n)<< endl;52 }53 54 return 0;55 }
在一次检验中，该算法出错的可能顶多是四分之一。如果我们独立地和随机地选择 a 进行重复检验，一旦此算法报告 n 是合数，我们就可以确信 n 肯定不是素数。但如果此算法重复检验 25 次报告都报告说 n 可能是素数，则我们可以说 n “几乎肯定是素数”。因为这样一个 25 次的检验过程给出关于它的输入的错误信息的概率小于 (1/4)25。这种机会小于 1015 分之一。即使我们以这样一个过程验证了十亿个不同的素数，预料出错的概率仍将小于百万分之一。因此如果真出了错，与其说此算法重复地猜测错，倒不如说由于 硬件的失灵或宇宙射线的原因，我们的计算机在它的计算中丢了一位。这样的概率性算法使我们对传统的可靠性标准提出一个问号：我们是否真正需要有素性的严格 证明。(以上文字引用自 Donald E.Knuth 所著的《计算机程序设计艺术 第2卷 半数值算法(第3版)》第 359 页“4.5.4 分解素因子”中的“算法P(概率素性检验)”后面的说明)
计算器里面有一个存储器，默认状态下是空的（即0）。它能保存任意一个数值，也只能存一个值。
MS：存当前显示的数值
MR：读取存储器中的数值，并显示出来
MC：清除已存的数据。
