怎么样求N以下所有素数

liangbch

9# fly
   不知你用这么多这么大的素数做什么用？如果你做RSA加密，不需要100%绝对的素数，非确定性素数判定算法足够用而且足够快，实时生成素数应该能够满足需要。如果你想预先计算出大量的素数存起来，需要的时候随机挑选一个，这就陷入两难抉择了，存储的数少了，不够随机，存得太多了，硬盘开销太大，如何做到平衡也很烦人。

fly

10# liangbch


我用的是google浏览器，不知道他支不支持latex。
如果可以的话，请告知怎么开

fly

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，返回循环重新生成
这应该要比“非确定性素数判定算法”来实时生成素数快（我直觉）。

fly

如果能用比较快的算法来随机生成2^2048以下的随机素数2^20个，也就解决了我的问题了

liangbch

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建议还是放弃这个念头吧。

fly

17# 风云剑

是2^20，13楼是typo。

fly

16# liangbch


我觉得可能是你误解了mpz_nextprime的用法，你的理解可能是有点问题的。因为这个mpz_nextprime真 的可能不是按你说的做，因为他要比你说的还要快。

非确定性素数判定算法(Miller-Rabin 测试)快于确定性素数算法，这个早有定论，没有什么好争的
不是跟你争这个，而是跟你争怎么实时生成素数，你说的用“非确定性素数判定算法足够用而且足够快，实时生成素数应该能够满足需要。”
我希望你本着严谨的精神把代码写出来，然后跟我的代码比比看，到底是谁的快。
用事实来说话更加可靠。

liangbch

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);   

liangbch

楼主总是不相信我说的，我就给出我刚刚写的一个调用GMP寻找素数的程序吧。
不管楼主怎么想，是不相信也好还是激将也好，总之，楼主应该有所收获，这里在VC 6.0下使用GMP的一个完整的事例。
  对GMP，我以前总是看的多实践的少，从没有写过一个调用GMP的程序。这次楼主的激将法起了作用，我不得不写一个调用GMP的程序了，从这点上，我还是非常感谢楼主。
  
  写给出测试结论。
  我这里的运行结果表明，计算2048bit以内的一个素数，仅需大约1秒的时间,GMP号称最快的大数运算库，我想，通过适当的优化算法，超过GMP应该是可能的，但改进的幅度应该不会太大。

下面是运行结果：
---------------------------------------------

1. n= 32317006071311007300714876688669951960444102669715484032130345427524655138867
   
2. 89089319720141152291346368871796092189801949411955915049092109508815238644828312
   
3. 06308773673009960917501977503896521067960576383840675682767922186426197561618380
   
4. 94338476170470581645852036305042887575891541065808607552399123930385521914333389
   
5. 66834242068497478656456949485617603532632205807780565933102619270846031415025859
   
6. 28641771167259436037184618573575983511523016459044036976132332872312271256847108
   
7. 20209725157101726931323469678542580656697935045997268352998638215525166389437335
   
8. 543602135433229604645318478604952148193555853611059596230655
   
9. r= 27362146563138776857982728818380223201396348785705792191523687503949678108173
   
10. 99940566127117505296267068718876291961676893039812711056372712009039337719266306
    
11. 53399251063408964938569898570955949825765798105272822671259918839693479216917782
    
12. 15703198021881656810310840682707715049113743235773157119149858759547571693709281
    
13. 43927777452078944320654156473491634280636501265834734763623385553721109784489079
    
14. 52215840890426806918941699802106381821686824635397622880353668553494998397486591
    
15. 72105286746228695779975747577204898312976788706805092864351507296077048907174491
    
16. 531725975477830513157574120773905306854649624870603675456789
    
17. q= 27362146563138776857982728818380223201396348785705792191523687503949678108173
    
18. 99940566127117505296267068718876291961676893039812711056372712009039337719266306
    
19. 53399251063408964938569898570955949825765798105272822671259918839693479216917782
    
20. 15703198021881656810310840682707715049113743235773157119149858759547571693709281
    
21. 43927777452078944320654156473491634280636501265834734763623385553721109784489079
    
22. 52215840890426806918941699802106381821686824635397622880353668553494998397486591
    
23. 72105286746228695779975747577204898312976788706805092864351507296077048907174491
    
24. 531725975477830513157574120773905306854649624870603675456839
    
25. 计算时间：1.084s

复制代码