millerrabin算法

㈠ Miller Rabin算法的优化实现

Miller-Rabin算法最为耗时的步骤在2.2模幂操作和2.3.2 循环。对算法的优化实现主要集中在对这两部分运算的优 化。对模幂操作的优化有两种途径：减少模幂算法中的模乘 操作和优化模乘操作。在求模幂的过程中不能先求幂最后一次求模，这样会产生一个十分巨大的中间结果，造成实际的 不可操作，所以在求模幂的算法中用模乘代替乘法，使得中 间结果的长度不超过模的长度。对模幂算法的优化，我们使 用改进的滑动窗口算法结合Montgomery模乘和模平方算法。表1给出模幂算法的比较。 模幂算法 预先计算 模平方 模乘法 模平方 模乘法 最坏情况 平均情况 平方乘算法滑动窗口类算法 改进的滑动窗口算法 011 02k -32k-1-1 tt-(k-1)≤次数≤t t-(k-1)≤次数≤t t (t/k)-1 (t/k)-1 t/2 t/k(2k-1)/ 2kk≤t/k(2 -1)/ * 模幂算法比较，其中k是窗口大小，根据情况 选择以达到最优，t是指数的二进制位数。 优化的模幂算法描述：输入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 窗口大小)输出： xe mod n1、预计算1.1、x1← MontMul(x， R2，n)，x2←MontSqu(x 1， n)1.2、对i 从1 到2k-1-1计算x2i+1←MontMul(x2i-1， x2，n)2、A←R，i ←t3、 当i≥ 0时作下面的操作： 3.1、如果ei=0，A←MontSqu(A ，n)，i← i-13.2、否则找到最长的位串eiei-1?es使得i-s+1≤k并且es=1,计算3.2.1、A <－A2i-s+1 ， (利 用MontSqu函数计算)3.2.2、A <－A*X(ee ...e )2 ，(利 用MontMul函数计算)3.2.3、i ←s-14、A←MontMul(A ，1 ，n)5、返回A其中MontMul(x,y,n) 是Montgomery模乘函数，函数输出 结果为x*y*R-1 mod n，MontSqu(x,n) 是Montgomery模平方函 数，输出结果为x2R-1 mod n。模乘算法如果采用大整数乘法 和除法求模乘，因为涉及耗时的除法操作，所以要相对较 慢，结合大整数乘法和Barrett求模算法可以用2(n2+3n+1) 步 单精度乘法完成。使用Montgomery求模算法结合大整数乘法 算法，可以 在 2n(n+1) 步单精度乘法内完成算法。 Montgomery模平方的操作可以在3n(n+1) /2步单精度乘法内 完成，而Barrett模平方需要(3n(n+3)/2+1) 步单精度乘法。结 合改进的滑动窗口算法和Montgomery类算法，可以得到目前 非特殊情况下的最优的模幂算法。在Miller-Rabin算法的2.3.2循环中的模平方操作我们没有 使用Montgomery模平方算法，因为该算法给出的结果带有R-1这个参数，在2.3.2循环中处理掉这个参数将占整个循环运 行时间中的很大部分，尤其是在循环的控制参数s 相对较小的时候。我们在这里使用大整数平方算法结合Barrett求模算 法，2.3.2的循环最坏情况需要(s-1)(3n(n+3)/2+1)步单精度乘法。

㈡ Miller Rabin算法的时间复杂度

Miller-Rabin算法是一个概率算法，算法的操作集中于 2.2步和2.3.2的循环中，最坏情况是2.3.2的循环没有中途退 出，则一轮Miller-Rabin算法的最坏情况时间复杂度为 (1+O(1))log2(n)( 以模n乘法为基本操作)。如果以单精度乘法操作作为时间复杂度的衡量，则一轮优化的Miller-Rabin算法的最 坏情况时间复杂度为O(log32 (n) 。从时间复杂度来看Miller- Rabin算法的性能是很好的。在实际应用中，Miller-Rabin 算 法的实际执行速度也很快。

㈢ Miller Rabin算法的算法基本框架

目前的基于概率的素数测试算法一般都遵循一种基本的 框架[1]。给定一个正奇数n，定义一个集合W(n)属于集合Z(n) (Z(n)是模n的非负整数集合)并有如下属性：(1) 给定一个属于集合Z(n) 的非负整数a ，可以在多项式时间复杂度内判断a 是否属于集合W(n) ；(2) 如果n是一个素数，那么Z(n) 中属于集合W(n) 的元素 的个数为0； (3)如果n是一个合数，那么Z(n)中属于集合W(n)的元素的个数大于等于n/2。如果n是一个合数，那么集合W(n) 中的元素叫作合数n 的证据，集合L(n)=Z(n)－W(n)中的元素叫作合数n的伪证。 基于概率的素数测试算法的基本思路是：定义一个符合以上规则的集合W(n)，对待测整数n随机选择属于集合Z(n)的元 素a，检查a 是否属于集合W(n)，如果a 属于W(n)则可以确定n 是一个合数，如果a不属于W(n) 则n是素数的可能性大于等于1/2。对n 随机地选择元素a相对独立地作 t 轮这样的测试，则n是素数的可能性可以被控制在 1-(1/2)t以上。

㈣ Miller Rabin算法的简介

Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时， Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin 算 法底层运算的优化，可以取得较以往实现更好的性能。随着信息技术的发展、网络的普及和电子商务的开展， 信息安全逐步显示出了其重要性。信息的泄密、伪造、篡改 等问题会给信息的合法拥有者带来重大的损失。在计算机中构建密码安全体系可以提供4种最基本的保护信息安全的服 务：保密性、数据完整性、鉴别、抗抵赖性，从而可以很大 程度上保护用户的数据安全。在密码安全体系中，公开密钥 算法在密钥交换、密钥管理、身份认证等问题的处理上极其有效，因此在整个体系中占有重要的地位。目前的公开密钥 算法大部分基于大整数分解、有限域上的离散对数问题和椭 圆曲线上的离散对数问题，这些数学难题的构建大部分都需 要生成一种超大的素数，尤其在经典的RSA算法中，生成的素数的质量对系统的安全性有很大的影响。目前大素数的生 成，尤其是随机大素数的生成主要是使用素数测试算法，本 文主要针对目前主流的Miller-Rabin 算法进行全面系统的分析 和研究，并对其实现进行了优化。

㈤ Miller Rabin算法的概率素数测试算法和真素数测试算法

素数测试算法主要分两种：概率素数测试算法和真素数测试算法。 概率素数测试算法的特点是：算法速度较快、原理简单、易于编程实现、有一定的误判概率。与之相比，真素数 测试算法最大的特点是不存在误判，但从应用角度讲，真素 数测试算法不如概率测试算法实用。最大的原因是：真素数 测试算法相对较慢。一些较快的真素数测试算法是针对某些特定类型的数设计的，如 ： Lucas-Lehmer 算法是针对 Mersenne数的测试算法，这类素数测试算法在密码学中的应 用很受限制。基于椭圆曲线和割圆环的真素数测试算法可以 用来测试任意的随机数，但这两类算法都很慢，目前最好的基于椭圆曲线的算法的时间复杂度是log n6+ ε(ECPP)，基于 割圆环的测试算法的时间复杂度log nclogloglogn。真素数测试算法背后的理论比较艰深，在计算机中的实 现十分复杂，实现复杂带来的不正确实现的安全隐患要比概率算法误判带来的安全隐患大得多。概率算法的误判完全可以被控制在一个极低的可接受的概率范围内，例如：控制误 判概率在2^-80以下足可以满足绝大部分的安全需求(密码学 的应用中不存在绝对的0误差，软、硬件实现中的各种不安全因素远远大于概率算法的误判)，加之概率算法速度快并 且实现相对容易，因此在实际应用中，大多使用基于概率的 素数测试算法。

㈥ 利用Miller-Rabin算法判断一个数是否为素数，但是结果经常把素数判断为合数，哪里有问题求指点

while(init)
{j++;
修改j＋＋为j＝1，每次循环的时候j重置为1

//if(j>0&&y==1){flag=1;break;}
while(init)
{j= 1;

㈦ Miller Rabin算法的在应用中的考虑

(i)(ii)p k ,1pk , tk 2 4 2k 3 / 2 2 tkfor k 2t 1 / 2 4 2 tk(iii) p 7 k 2 5t k , t201 k15 / 4 27k / 2 2 t12 k 2k / 4 3tfor k / 9(iv) pk , tt k / 4, k1 k15 / 4 2721k / 22t for tk / 4, k 21Miller-Rabin算法的应用主要集中在构建密码安全体系的素数生成模块中，当输入的待测数n是很大(例如： 1024bits)的随机数的时候，算法的误判概率远远小于上面给出的理论 上的误判概率上界。设Pk,t 代表(k=log2 n，t是测试的轮数)在 素数生成算法中应用t轮Miller-Rabin 算法给出错误结果的概 率，则有如上所示的误判概率公式。在一般的密码安全体系中，误判概率小于 (1/2)就可以满足安全需求。表2给出了当p(k,t) ≤ (1/2)80的时候对应的k和t的值。
表2 k,t对应值 k 100 150 200 25 300 350 400 450 550 650 850 1300 t 27 18 15 12 9 8 7 6 5 4 3 2 在基底的选择上，因为以2作为基底可以剔除很大部分 合数，并且对以2为底的模幂的运算很快，所以可以考虑在 应用中固定使用基底2，其它基底随机选择，这样的改进可 以提高算法的运行速度。

㈧ Miller Rabin算法的算法比较

Miller-Rabin算法在基于Fermat定理的算法中是最优秀的，无论从误判概率还是从速度上看，它都优于其它 Fermat 类算法，例如 ： Fermat 算法 、 Lehmann 算法、 Solovay- Strassen算法等。Lucas 测试是Pomerance、Selfridge 和 Wagstaff 提出的一种基于Lucas序列的概率素数测试算法，该算法一轮消耗的 时间大概相当于6轮Miller-Rabin测试。一轮Lucas 的误判概率 为4/15，该算法经过一些改进,一轮的误判概率达到1/8。这 种算法在误判概率和速度的权衡考虑上不如Miller-Rabin 算法。Grantham-Frobenius 测 试(QFT) 是 Grantham 提出的基于 Frobenius概率素数和Frobenius强概率素数理论的算法，给定 一组参数(b,c)，误判概率可以被控制在1/7710以下。时间复杂度是(3+O(1))log2(n)( 以模n乘法为基本操作)，大概相当于3轮Miller-Rabin算法。这种算法理论比较艰深，目前只停留在理论研究阶段，还不适合现实应用。Adams 和Shanks 提出了一种基于Perrin 序列的算法，他们算法的Q和I两种情况下还没发现伪素数，没有考虑算法 的速度，只是就误判概率来进行研究，他们的工作主要是侧 重数学理论研究，算法目前还不适合现实应用。

㈨ 有关Miller-Rabin算法

在《现代密码学-原理与协议》这本书里看到过类似结论的证明. （7.38）

不过这个1/2不是针对1~n-1的整数集，而是针对1~n-1中元素构成的模n的乘法群Zn*，这个群中仅有那些满足gcd(a, n) = 1这个条件的元素a。另外，需假设n若n为合数，则至少有一个证据证明它是合数。

需要一点群论的知识

1. 若G为有限群，假设H含有G的“1”(幺元)，且对于H中任意的a、b恒有ab属于H，则H是G的子群

2. 若H为有限群G的真子群，则|H| <= |G/2|. （| |代表元素数)

证明：

定义Bad为乘法群Zn*中，不是"n为合数"的证据的元素的集合。（即满足 a^(n-1) = 1 mod n）

显然，1 属于 Bad。

若a,b属于Bad, 则 (ab) ^ (n-1) = a^(n-1) * b^(n-1)= 1*1 mod n =1 mod n

所以 ab 也属于 Bad

由 1 可得 (Bad, *)是Zn*的一个子群

而因为若n为合数，则至少有一个1~n-1中的数使a^(n-1) 不等于 1 mod n，因此Bad为Zn*的真子群

再由2可得 Bad中元素数小于等于Zn*元素数的一半

那么，反过来，Zn*中可以成为证据的元素至少占Zn*中全体元素的1/2

维基网络Miller-Rabin的英文词条下面的参考文献中，他们的原始论文里有完整的对于n为奇合数的判定成功概率的完整证明

㈩ Miller Rabin算法的误判概率

经过独立的t轮Miller-Rabin算法将一个合数误判为素数的可能性不大于 (1/4)t，(正确实现的算法不会误判素数为合 数)，这个误判概率在基于Fermat定理的算法中是最好的。这个误判概率是利用下面两个定理证明的：定 理 1 ：设d=gcd(k,m) ，那么在有限群{g,g2,g3,?,gm=1}中(g是有限群的生成元，m是有限群的阶) 有d个元素x满足方程式xk=1。定 理 2 ： 设p是一个奇素数，p-1=2sh(h是奇数)，那么在乘法群(Z/pZ)*中满足方程式 x2rt=-1mod p(t是奇数 )的元素的个数是：0，如果r ≥s；2rgcd(h,t)，如果r<s。 利用这两个定理，对算法输入n分3种情况讨论：(1)n可以被某个素数的平方整除的时候; (2)n是两个不同素数的乘积的时候;(3)n是两个以上不同素数乘积的时候。这样可以证明Miller-Rabin算法的误判概率上界。