如何采用Rabin-Miller算法并行判断一个数为素数?加分 如题 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 根据算法描述来Rabin -Miller算法是典型的验证一个数字是否为素数的方法。判断素数的方法是Rabin-Miller概率测试,那么他具体的流程是什么呢。假设我们要判断n是不是素数,首先我们必须保证n 是个奇数,那么我们就可以把n 表示为 n = (2^r)*s+1,注意s 也必须是一个奇数。然后我们就要选择一个随机的整数a (1<=a<=n-1),接下来我们就是要判断 a^s=1 (mod n) 或a^((2^j)*s)= -1(mod n)(0<=j如果任意一式成立,我们就说n通过了测试,但是有可能不是素数也能通过测试。所以我们通常要做多次这样的测试,以确保我们得到的是一个素数。(DDS的标准是要经过50次测试) 采用Rabin-Miller算法进行验算首先选择一个代测的随机数p,计算b,b是2整除p-1的次数。然后计算m,使得n=1+(2^b)m。(1) 选择一个小于p的随机数a。(2) 设j=0且z=a^m mod p(3) 如果z=1或z=p-1,那麽p通过测试,可能使素数(4) 如果j>0且z=1, 那麽p不是素数(5) 设j=j+1。如果j且z<>p-1,设z=z^2 mod p,然后回到(4)。如果z=p-1,那麽p通过测试,可能为素数。(6) 如果j=b 且z<>p-1,不是素数 空指针异常,看了好久好久,实在看不出来,求帮助 SWT的image如何按比例缩小? 两道关于java的初始化顺序问题的题。(第一次发贴,大家支持一下) java数据库连接问题 选定区域截图 如何将查询结果放到另外的表中(用java实现),谢谢 ~~~~在swing中如何做仪器系统面板的显示? 请大家帮忙解决一个问题! apache1.3+tomcat4的问题,所有文件都配置好之后,examples应用可以正常,但我自己建的app即不能使用,为何?错误如下: 5分钟,得100分,来者有分 聊天室jsp代码 如何设置JtextField可以输入的字符宽度
采用Rabin-Miller算法进行验算
首先选择一个代测的随机数p,计算b,b是2整除p-1的次数。然后计算m,使得n=1+(2^b)m。
(1) 选择一个小于p的随机数a。
(2) 设j=0且z=a^m mod p
(3) 如果z=1或z=p-1,那麽p通过测试,可能使素数
(4) 如果j>0且z=1, 那麽p不是素数
(5) 设j=j+1。如果j且z<>p-1,设z=z^2 mod p,然后回到(4)。如果z=p-1,那麽p通过测试,可能为素数。
(6) 如果j=b 且z<>p-1,不是素数