荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: 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软件 网络书店