计算器中mr是什么意思

发布网友 发布时间：2022-03-28 12:34

我来回答

共2个回答

热心网友 时间：2022-03-28 14:03

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(概率素性检验)”后面的说明)

热心网友 时间：2022-03-28 15:21

计算器里面有一个存储器，默认状态下是空的（即0）。它能保存任意一个数值，也只能存一个值。

MS：存当前显示的数值

MR：读取存储器中的数值，并显示出来

MC：清除已存的数据。