荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Version (Who makes history and why), 信区: Program
标 题: Re: 求素数的最快的算法是什么？(zz)
发信站: 荔园晨风BBS站 (Tue Mar 25 18:00:23 2003), 站内信件
查表和试除都不太可行（空间复杂度和时间复杂度）
一般也没有特别有效的办法，我记得RSA中是利用费马小定理
来做判定的，基本原理是这样的
假设数p,
如果p是质数，那么 a ^ p == a mod p
如果p不是质数，那么 a ^ p == a mod p成立的概率很小，而且 p
越大概率越小，这样用 2 ^ p == 2 mod p, 3 ^ p == 3 mod p,....
成立的话，基本（？）上可以判定 p 是质数
具体的实现方法好象网上有一个RSAEuro的程序，用C写的，已经做
的比较清楚了:)
【 在 Version (Who makes history and why) 的大作中提到: 】
: 我采用的大质数的求取方法如下：
: 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软件 网络书店