Simone计算器中mr是什么意思
的有关信息介绍如下：
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 2 #include 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> 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(概率素性检验)”后面的说明)
