素数检测算法报告

《素数检测算法报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、素数检测算法的学习报告素数是指在自然数中，除了1和它自身外，没法被其他自然数整除的数。在这几天查阅书籍和一些相关的网络资源中，对素数的检测算法有了很深入的了解，因为大部分资料是在网上找到的，所以将“读书报告”改为“学习报告”，望老师谅解。对于素数的检测算法有很多，先前有很多人研究过这些，我相信以后还会有很多人来研究，以下内容是我国庆这几天，在空闲时读到的算法的一个总结。1・试除法来判定素数。这种方法是我们常用的方法，思路是用循环将已知数与比其小的数相除，判断余数是否为零，为零则不是素数，不为零则为素数。相关代码如下：#include#includeHmath.hH

2、voidmain(){inti,k,n;intflag=l;cout«n输入一整数:n«endl;cin»n;k=sqrt(n);〃用n除以比他小的每一个也可以，实际除以n的开方就可以for(i=2;iv=k;i++)if(n%i==O){flag=O;cout«n此数不是素数！"vvendl;}if(flag)cout«n此数是素数!H«endl;}程序已经过调试，正确。但是该算法的时间复杂度为O(sqrt(n)),当n较大吋，吋间性能很差，特别是在网络安全和密码学上一般都是需要很大的素数。2.筛选法还判定素数。现在我们用筛选法来求2〜n之间的所有素数。思路为：我们将每一个数都视为是素

3、数，从小到大，一次判断，假设i是素数，那么i的倍数就不是素数，依次判断到n就可以找到2〜n的所有素数了。相关实现代码如下：#include#include"math.h"voidprime(intn);voidmain()intk;cout«n输入一正整数(>2):H;cin»k;cout«n2—n«k«n之间的素数为:H«endl;prime(k);}voidprime(intn){int*isPrime=newint[n4-l];//isPrime相当于标记的作用，用来标记素数for(inti=2;i<=n;++i){isPrime[i]=1;for(intj

4、=2;j<=n;++j)if(isPrime[j]=l)for(intm=2;j*mv=n;++m)〃倍数不是素数isPrimefj*m]=0;if(isPrime[i]==l)cout«i«endl;}程序已调试完毕，正确运行。但是对于大批量的数据则无法显示,比如：输入123456789则不会显示，也就是这种方法也解决不了大素数的问题。2.Miller-Rabin算法Miller-Rabin算法是很经典的解决方法•下面就介绍一下他的具体方法和相关理论。1)费马小定理如果P是一个素数，且Ovavp,贝！JaA(p-l)=l(modp)费马小定理只是个必要条件，符合费马小定理而非素数的数叫

5、做Carmichael.前3个Carmichael数是561,1105,1729oCarmichael数是非常少的。在1-100000000范围内的整数中，只有255个Carmichael数。为此又有二次探测定理,以确保该数为素数。2)二次探测定理如果p是一个素数，Ovxvp,贝IJ方程xA2=l(modp)的解为x=l,p・l下面具体说一下算法的步骤是我们要测试的数据：1、先计算出m、j,使得n-l=m*2Aj,其中m是正奇数，j是非负整数2、随机取一个b,2<=b3、计算v=t)Ammodn4、如果v==l,通过测试，返回5、令i=l6、如果v=n-l,通过测试，返回7、如果i==j

6、,非素数，结束8、v=vA2modn,i=i+l9、循环到510、进行5轮验证，则n以99.9%以上的概律为素数具体的算法实现和更加简单易懂的描述在实验报告中写出。4.RSA算法这种算法出现的很早，大约在1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdlemano但RSA的安全性一直未能得到理论上的证明。RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数(大于100个十进制位)的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两

7、个大素数的积。密钥对的产生。选择两个大素数，p和q。计算：n二p*q然后随机选择加密密钥e,要求e和(p-1)^(q-1)互质。最后，利用Euclid算法计算解密密钥d,满足e*d=1(mod(p-l)*(q-l))其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息m(二进制表示)时，首先把m分成等长数据块ml,m2,…,mi,块长s,其中2As<=n,s尽可能的大。对应的密文