搜索
1问题及算法1.1问题描述为了解决普通算法无法正确求出大素数的问题，我们现在用改进后的Miller-Rabin算法来很好的解决了大素数的问题。1.2算法思路描述由费马小定理知：若n是素数，则对所有1≤a≤n-1的整数a，有a^(n-1)modn=1。该定理的逆否命题也成立，即a^(n-1)modn!=1，则n为合数。但是费马定律的逆命题就不一定成立了，比如当a=4，n=15时,4^14mod15=1,但是4不是素数而是合数。也就是说直接用费马定理求解素数的话，是有一定的错误率的，现在我们的目标的尽量减少错误率。从大量数据统计来看，如果满足a^(n-1)modn=1，则n较大概率为素数.那么，我们把那些使得n原本为合数而被看成素数的a叫做伪证据，称n为伪素数。同样从大量数据看出有些伪素数n有很多伪证据a，比如当n=561，a有318个可使得结果判为素数。所以，我们定义了强伪素数概念：设n是一个大于4的奇整数，s和t是使得(n-1)=2^s*t的正整数，其中t为奇数，设B(n)是如下定义的整数集合：a属于集合B(n)当且仅当2≤a≤n-2且1．a^tmodn=12．存在整数i，0≤is满足a^((2^i)*t)modn=n-1当n为素数时，任意a在2和n-1中，均有a属于集合B(n)。当n为合数时，若a属于集合B(n)，则称n为一个以a为底(基)的强伪素数，称a为n素性的强伪证据。n为素数，说明它对所有底均为强伪素数。通过这一定义则发现，小于1000的奇合数中，随机选到一个强伪证据的概率小于1%。更重要的是，对任一奇合数，强伪证据比例都很小。所以,我们可以多次运行下面的算法,就可把错误概率降低我们可控制的范围，这样我们就有效的解决了大素数求解的问题。1.3算法实现的关键技巧此算法实现的关键技巧在于强伪素数的定义以及巧妙的应用。Btest(a，n){//n为奇数，返回true。即返回真说明n是强伪素数s←0；t←n-1；//t开始为偶数repeats++；t←t÷2；untiltmod2=1；//n-1=2stt为奇数x←atmodn；ifx=1orx=n-1thenreturntrue;//满足强伪素数定义1或者2.fori←1tos-1do{x←x2modn；ifx=n-1thenreturntrue；//满足强伪素数定义2}returnfalse；}用下面的定义方式可以使判断错误概率为(1/4)^k，正确的为1-(1/4)^k。当k取一定值时，判断正确的概率可高度99.99%。MillRab(n){//奇n4，返回真时表示素数，假表示合数a←uniform(2..n-2);returnBtest(a,n);//测试n是否为强伪素数}//该算法是3/4-正确，偏假的。RepeatMillRob(n,k){fori←1tokdoifMillRob(n)=falsethenreturnfalse;//一定是合数returntrue；}2实验结果与分析2.1实验数据及结果1）输入小于3的数时，比如0,1，以及任意大的负数。结果：屏幕打印输出：2）当输入小数时（比如100.8）结果：程序输出2~100内的素数。3）当输入值大于等于9时结果：输出结果会有94）当输入数为100位时结果：程序仍能正常运行。2.2实验分析及结论1）输入小于3的数时，会提示你重新输入。说明：在获取数据上程序具有一定安全性。2）当输入小数时（比如100.8），程序输出2~100内的素数。说明：程序会默认输入为100，也就是舍去小数不考虑，并非四舍五入。3）当输入值大于等于9时，输出结果会有9。说明：程序还是有一定错误率，虽然这个错误率很低。4）当输入数为100位时，程序仍能正常运行。说明：程序可用范围很大，符合我们求大素数的要求。总体来看程序的安全性比较高，而且满足了我们对大素数的要求，算法的效率也比较高，准确率比未改进前有了很大的提高。3心得与展望3.1自我评价及心得体会自我评价：1）对基础知识掌握不牢，思维不灵活，尤其在如何提高算法正确率问题上，考虑的比较简单和单一。2）写程序时，未按照格式来写，给纠错和阅读带来很大困难。3）程序运行成功后，按常规思路来检验程序，未能考虑周全，考虑各方面的数据。心得体会：对一个问题要多思多想，很多问题解法都不只一种，要努力找到一个正确性和效率都比较高的算法。写程序时按照格式来写，这样方便对于程序的阅读和改错，提高程序可读性和调试的效率。考虑问题要全面，测试数据不要只用简单的数据测试，还要用些大数字、负数、特殊数字等等来测试。做一个问题也要坚持，不要今天做一点明天做一点，否则会很浪费时间，效率也很低。3.2展望未来的路还有很长要走，对于素数的研究工作也没有到此结束，以后还会有更多更好的算法出现，当然这都需要大家的共同努力！就像俗语说的那样：道路是曲折的，前途是光明的！参考文献[ll.谭浩强.C++程序设计.北京:清华大学出版社;2004.[2].孙鑫.VC++深入详解.北京：电子工业出版社;2006.[3].刘弘.面向对象程序设计.北京：北京邮电大学出版社;2005.[4].=278294[5].[6].[7].[8].[9].[10].[11].[12].[13].