rabbin素数判定算法

《rabbin素数判定算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Java算法——判断素数(RabinMiller和一些基本的判定方法)publicstaticbooleanisPrimeNumber(intnumber){    if(number<2)        returnfalse;    for(inti=2;i<=Math.sqrt(number);i++){        if(number%i==0&&number!=2)            returnfalse;    }    returntrue; }素数算法（二）上次讨论了简单的素数判定的算

2、法，不过这个算法对于位数较大（一般小于108）的素数判定就显得相当力不从心了。比如在素数目前最广泛的应用领域-公共密钥体系中，一般选择的素数都是相当大的（通常在100位以上），如果采用上次的试除法来判定，那么可能要穷尽你一生的时间都还不够。所以在一般的应用领域，人们采用的是Rabin-Miller检验法。下面是该检验法的算法：首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。（1）选择一个小于p的随机数a。（2）设j=0且z=a^mmodp（3）如果z=1或z=

3、p-1，那麽p通过测试，可能使素数（4）如果j>0且z=1,那麽p不是素数（5）设j=j+1。如果jp-1,设z=z^2modp，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。（6）如果j=b且z<>p-1，不是素数数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。实际考虑：在实际算法，产生素数是很快的。（1）产生一个n-位的随机数p（2）设高位和低位为1（设高位是为了保证位数

4、，设低位是为了保证位奇数）（3）检查以确保p不能被任何小素数整除：如3，5，7，11等等。有效的方法是测试小于2000的素数。使用字轮方法更快（4）对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机数a,在测试。选取较小的a值，以保证速度。做5次Rabin-Miller测试如果p在其中失败，从新产生p，再测试。经测试，这个算法在sun的SparcII工作站上实现：2.8秒产生一个256位的素数24.0秒产生一个512位的素数2分钟产生一个768位的素数5.1分钟产生一个1024位的素

5、数最近在网上看了不少关于素数的问题，也学习到了不少东西，决定整理一下，算是一个学习的总结吧。首先想说明的是，虽然素数可以进行很深入的研究（如在RSA公共密钥系统的应用），但是由于我对数论的不甚熟悉，所以只能做一些浅尝辄止的探讨，主要就是对一些简单的素数相关算法进行一个讨论。首先来说说素数的判定算法，如果你是读谭浩强老师的《c程序设计》入门的话，那么一谈到素数的判定算法，你首先应该想到的就是以下的算法：给定一个正整数n，用2到sqrt(n)之间的所有整数去除n，如果可以整除，则n不是素数，如果不可以整除，则n就

6、是素数。这个算法的时间复杂度十分明了，为O（sqrt（n）），算法的描述相当简单，实现也一样不困难。#include#includeintisPrime(intn){   inti;    for(i=2;i<=sqrt(n);i++){       if(n%i==0)           break;   }   if(i<=sqrt(n))       printf("%disnotaprime!",&n);   else       printf("%disaprim

7、e!",&n);    return0;}=====================================publicclass SuShu{   privateintnum;  SuShu(intn){    num=n; }  public booleanisSuShu(){ for(inti=2;i

8、(String[]args){    for(inti=1;i<=100;i++){  SuShusu=newSuShu(i);  if(su.isSuShu())   System.out.println(i+"是素数");  else   System.out.println(i+"不是素数");    } }}=============================/**  *@paramn