9# fly
不知你用这么多这么大的素数做什么用？如果你做RSA加密，不需要100%绝对的素数，非确定性素数判定算法足够用而且足够快，实时生成素数应该能够满足需要。如果你想预先计算出大量的素数存起来，需要的时候随机挑选一个，这就陷入两难抉择了，存储的数少了，不够随机，存得太多了，硬盘开销太大，如何做到平衡也很烦人。
10# liangbch
我用的是google浏览器，不知道他支不支持latex。
如果可以的话，请告知怎么开
11# liangbch
公钥加密体系的加密算法不仅仅有RSA而已，还有其他的很多，比如：ElGamal encryption.肯定是有加密算法这么要求啦
至于在这么大的素数做什么，那是用来做为加密的随机参数的。这个加密的随机参数要求是素数，那当然要求是N以下的素数了。
你说的“非确定性素数判定算法”来实时生成素数，你觉得这个对于2^2048这么大的范围还是有效率的吗？很在可能随机的数都不是素数。而且我的实验要求要生成10^20个随机素数，因为我要加密10^20次。这样，还不如我自己在一楼写的那个程序。
gmp_randinit_default(state); 设置随机初始状态
do
{
mpz_urandomm(r, state, N); 得到N以下随机一个数，赋给r
mpz_nextprime(r, r); 求得r的下一次素数，赋给r
}
while(mpz_cmp(r, N)>=0); 如果r>N，返回循环重新生成
这应该要比“非确定性素数判定算法”来实时生成素数快（我直觉）。
如果能用比较快的算法来随机生成2^2048以下的随机素数2^20个，也就解决了我的问题了
13# fly
你可能误解了mpz_nextprime的用法，按我的理解，
GPM 函数 mpz_nextprime采用的非确定性素数判定算方法。op是入参，rop是出参。
比如，op=112, 得到的rop是113, op=127, 得到的rop是127，因为127是第一个比113大的素数。
GMP帮助文档
void mpz_nextprime (mpz t rop, mpz t op)
Set rop to the next prime greater than op.
This function uses a probabilistic algorithm to identify primes. For practical purposes it’s
adequate, the chance of a composite passing will be extremely small.
--------------------------------
非确定性素数判定算法(Miller-Rabin 测试)快于确定性素数算法，这个早有定论，没有什么好争的。
100万个素数不多。事先计算出来的时间代价和存储代价都不多。可你为什么要求“怎么样求N以下所有素数”
13楼说10^20个，14楼又变成了2^20个。
到底要多少个？
2^20还好说，10^20建议还是放弃这个念头吧。
17# 风云剑
是2^20，13楼是typo。
16# liangbch
我觉得可能是你误解了mpz_nextprime的用法，你的理解可能是有点问题的。因为这个mpz_nextprime真 的可能不是按你说的做，因为他要比你说的还要快。
非确定性素数判定算法(Miller-Rabin 测试)快于确定性素数算法，这个早有定论，没有什么好争的
不是跟你争这个，而是跟你争怎么实时生成素数，你说的用“非确定性素数判定算法足够用而且足够快，实时生成素数应该能够满足需要。”
我希望你本着严谨的精神把代码写出来，然后跟我的代码比比看，到底是谁的快。
用事实来说话更加可靠。
本帖最后由 liangbch 于 2011-6-17 10:47 编辑
21# fly
你说的和代码不一回事。
我强调的你下面的代码几乎是一个无限循环。
如果N=2^2048, r为N以内的一个随机数,q为比r只大一点点的素数，则q比N大的概率几乎为0。
按你的例子来，你的N是4000比特的一个数，而生成是随机数是一个2052比特的数，这个循环怎么能够终止呢？
注在6-17 10：47：上面的内容的确错了，sorry, 应该是只循环一次
而你说的是15分钟生成一个素数。
do
{
mpz_urandomm(r, state, N); 得到N以下随机一个数，赋给r
mpz_nextprime(r, r); 求得r的下一次素数，赋给r
}
while(mpz_cmp(r, N)>=0);
楼主总是不相信我说的，我就给出我刚刚写的一个调用GMP寻找素数的程序吧。
不管楼主怎么想，是不相信也好还是激将也好，总之，楼主应该有所收获，这里在VC 6.0下使用GMP的一个完整的事例。
对GMP，我以前总是看的多实践的少，从没有写过一个调用GMP的程序。这次楼主的激将法起了作用，我不得不写一个调用GMP的程序了，从这点上，我还是非常感谢楼主。
写给出测试结论。
我这里的运行结果表明，计算2048bit以内的一个素数，仅需大约1秒的时间,GMP号称最快的大数运算库，我想，通过适当的优化算法，超过GMP应该是可能的，但改进的幅度应该不会太大。
下面是运行结果：
---------------------------------------------n= 32317006071311007300714876688669951960444102669715484032130345427524655138867
89089319720141152291346368871796092189801949411955915049092109508815238644828312
06308773673009960917501977503896521067960576383840675682767922186426197561618380
94338476170470581645852036305042887575891541065808607552399123930385521914333389
66834242068497478656456949485617603532632205807780565933102619270846031415025859
28641771167259436037184618573575983511523016459044036976132332872312271256847108
20209725157101726931323469678542580656697935045997268352998638215525166389437335
543602135433229604645318478604952148193555853611059596230655
r= 27362146563138776857982728818380223201396348785705792191523687503949678108173
99940566127117505296267068718876291961676893039812711056372712009039337719266306
53399251063408964938569898570955949825765798105272822671259918839693479216917782
15703198021881656810310840682707715049113743235773157119149858759547571693709281
43927777452078944320654156473491634280636501265834734763623385553721109784489079
52215840890426806918941699802106381821686824635397622880353668553494998397486591
72105286746228695779975747577204898312976788706805092864351507296077048907174491
531725975477830513157574120773905306854649624870603675456789
q= 27362146563138776857982728818380223201396348785705792191523687503949678108173
99940566127117505296267068718876291961676893039812711056372712009039337719266306
53399251063408964938569898570955949825765798105272822671259918839693479216917782
15703198021881656810310840682707715049113743235773157119149858759547571693709281
43927777452078944320654156473491634280636501265834734763623385553721109784489079
52215840890426806918941699802106381821686824635397622880353668553494998397486591
72105286746228695779975747577204898312976788706805092864351507296077048907174491
531725975477830513157574120773905306854649624870603675456839
计算时间：1.084s