荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Version (Who makes history and why), 信区: Program
标 题: 求素数的最快的算法是什么？(zz)
发信站: 荔园晨风BBS站 (Tue Mar 25 17:59:48 2003), 站内信件
我采用的大质数的求取方法如下：
1.随机生成一个指定位数的大数。将最高位和最低位置1。
注：质数的密度约为lnN,N为此质数的位数。因此一个随机数是质数的概率
还是比较高的。
2.利用查表法，判断此随机数是否会被小于5000的质数整除。如果能够除尽，
就另选一个随机数进行测试。
注：这样可以排除85%以上的奇数。
2.利用查表法，判断此随机数是否会被小于5000的质数整除。如果能够除尽，
就另选一个随机数进行测试。
注：这样可以排除85%以上的奇数。
3.执行Rabin-Miller素数测试，大约5-6次就可以了。
注：理论上通过测试的随机数是合数的概率不超过2^51(256位素数，6次
测试）。有关算法描述可以参考Bruce Schneier著的应用密码学。
另，某些要用到的算法问题及其优化主要有以下几个：
1.大数乘法，精心优化后可使复杂度降到N^1.58。
2.大数求模，利用移位合并可以降低算法的平均复杂度。
3.大数减法，必须使用补码运算。
4.大数模幂乘，通过预处理可是算法复杂度降置N。
--
*
* *
* *
no more to say
★ just wish you ★
good luck
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.50]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店