怎么样求N以下所有素数

liangbch

这里给出完整的代码。

1. #include <stdio.h>
   
2. #include <tchar.h>
   
3. #include <windows.h>
   
4. #include <stdlib.h>
   
5. #include <time.h>
   
6. 
   
7. #include "include/gmp.h"
   
8. #pragma comment( lib, "lib/gmp.lib" /*"lib/gmp.lib"*/ )
   
9. 
   
10. #define MAX_BIT  2048
    
11. 
    
12. void SetFullF(char *p, int sizes) //全部填充为F
    
13. {
    
14.         p[0] = 'F'; //保证达到特定大小
    
15.         for (int i = 0; i < sizes; i ++)
    
16.         {
    
17.                 p[i] = 'F';
    
18.         }
    
19.         p[i]=0;
    
20. }
    
21. 
    
22. void test_findPrime()
    
23. {
    
24.         mpz_t gmp_N, gmp_r, gmp_q;
    
25.         gmp_randstate_t state;
    
26.        
    
27.         LARGE_INTEGER CountFreq, start, stop;
    
28.         double UsedTime;
    
29.         int bits;
    
30.         char *pA;
    
31.        
    
32.         bits=MAX_BIT;
    
33.         QueryPerformanceFrequency(&CountFreq);
    
34.         SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
    
35.        
    
36.         gmp_randinit_default(state);  //设置随机初始状态
    
37.        
    
38.         //初始化
    
39.         mpz_init(gmp_N);
    
40.         mpz_init(gmp_r);
    
41.         mpz_init(gmp_q);
    
42.        
    
43.         pA = (char *)malloc( bits/4 + 1 );
    
44.         SetFullF(pA, bits/4);
    
45.         mpz_set_str(gmp_N, pA, 16);
    
46.        
    
47.         QueryPerformanceCounter(&start);
    
48.         mpz_urandomm(gmp_r, state, gmp_N);   //得到N以下随机一个数，赋给r
    
49.         mpz_nextprime(gmp_q, gmp_r);             //求得r的下一次素数，赋给q
    
50.         QueryPerformanceCounter(&stop);
    
51.         UsedTime = (double)(stop.QuadPart - start.QuadPart) / (double)CountFreq.QuadPart ;
    
52.        
    
53.         gmp_printf ("n= %Zd\n", gmp_N);
    
54.         gmp_printf ("r= %Zd\n", gmp_r);
    
55.         gmp_printf ("q= %Zd\n", gmp_q);
    
56.         printf("计算时间：%.3fs\n", UsedTime);
    
57.        
    
58.         mpz_clear(gmp_N);  //释放内存
    
59.         mpz_clear(gmp_r);  //释放内存
    
60.         mpz_clear(gmp_q);  //释放内存
    
61. }
    
62. 
    
63. 
    
64. int main(int argc, _TCHAR* argv[])
    
65. {
    
66.         test_findPrime();
    
67.         return 0;
    
68.         return 0;
    
69. }

复制代码

liangbch

附加的信息：
1.我的代码参考了 http://bbs.emath.ac.cn/viewthread.php?tid=208
  2. Windows下的GMP .h文件和.lib,.dll 文件下载自http://www.cs.nyu.edu/exact/core/gmp/
  3. 环境配置。在源代码下创建include 和 lib目录 并 复制dll文件到编译后可执行文件所在的目录。复制.h文件的到源代码下的./include目录，复制lib文件到./lib目录。

软件环境：Windows XP 2000 SP2, VC++6.0
硬件环境：Intel Core 2 Duo E8500， 4G内存。

gxqcn

因为要求“随机”，前后无关联，所以不好利用现成已有数据，
随机素数就按楼主的方法生成就可以了。

由于加解密的bits一般不会太高，所以速度一般是可以有保障的，
除非是频率非常低的嵌入式设备。

fly

22# liangbch


大哥，你确定懂C语言吗？我很难理解你说的不能终止啊？？
那不能终止我为什么还能算出来。
你有没有把我的代码在你的计算上运行一下，看看真的不能终止呢？

呃，难道你不知道mpz_cmp的用法？？我贴给你看吧
int mpz_cmp (mpz t op1, mpz t op2)
Compare op1 and op2. Return a positive value if op1 > op2, zero if op1 = op2, or a negative
value if op1 < op2.

还是你不清楚do,while的语法？？
do……while（表达式）的意思是如果表达式为真，则返回循环，否则跳出

我的代码的意思是
1. 随机生成一个N以下的整数r
2. 找到r的下一个素数r'
3. 如果r'比N大（你说这个概率为几乎为0，但你能保证概率是为0吗？我要的是绝对素数，不是几乎可能是素数），则返回1，2，否则跳出，得到一个比N小的素数。

概率几乎为0就等于我的循环几乎不用循环

fly

24# liangbch


我觉得啊（个人感觉）
你的代码里面除了
        mpz_urandomm(gmp_r, state, gmp_N);   //得到N以下随机一个数，赋给r
        mpz_nextprime(gmp_q, gmp_r);             //求得r的下一次素数，赋给q
以外，其他的真正对算法有帮助的好像没有了。（这两句还是跟我一样的）
而且也找不到你说的“非确定素数判定法”的影子。（因为我的代码的读写能力很弱，可能看错了）
就算是有，我不觉得“非确定素数判定法”还能对已经产生的素数gmp_q有什么帮助？？
所以你的代码实际上是我的代码的不完全版本。（我感觉，可能不对）

而且，如果gmp_r＝N－10（可能性小，但是毕竟会发生的，因为我加密是成千上万次的），你觉得你的算法会产生比N小的素数吗？

不过你的速度好快，我要把试试看，看为什么我的会比你慢，因为从代码上来说，我的只会比你快的。

还是从你发的贴的获益不少，谢谢你！

fly

24# liangbch

这次用的时间不用一秒了，即时显示，我的计算机配置比你的差，用你的机子跑，应该更快。
原来是我的那些加密，解密，模幂用的时间长啊，郁闷啊

the modulus: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656


the Random: 27362146563138776857982728818380223201396348785705792191523687503949678108173999405661271175052962670687188762919616768930398127110563727120090393377192663065339925106340896493856989857095594982576579810527282267125991883969347921691778215703198021881656810310840682707715049113743235773157119149858759547571693709281439277774520789443206541564734916342806365012658347347636233855537211097844890795221584089042680691894169980210638182168682463539762288035366855349499839748659172105286746228695779975747577204898312976788706805092864351507296077048907174491531725975477830513157574120773905306854649624870603675456839




主要代码如下，其他的头文件什么的不贴了
        mpz_t n, r;
        mpz_init(n);
        mpz_init(r);
        mpz_ui_pow_ui(n,2,2048);
        gmp_randstate_t state;               
        gmp_randinit_default(state);
        do
        {
                mpz_urandomm(r, state, n);
                mpz_nextprime(r, r);
        }
        while(mpz_cmp(r, n)>=0);
        gmp_printf("\n\nthe modulus: %Zd\n", n);
        gmp_printf("\n\nthe Random: %Zd\n", r);

        mpz_clear(n);
        mpz_clear(r);

fly

23# gxqcn

牛人，见解好透彻！

你的意思是不是说如果要生成2^20个N以下素数，用我的代码重复2^20次就可以了吗？

唉，我就是想得到这样一些比较实际有用的建议。

liangbch

26# fly

我的确理解错了do while 循环。
郑重向楼主致歉。我删除了我错误的断言。

liangbch

27# fly

  mpz_nextprime采用的是概率算法，即非确定性算法。16#的GMP帮助文档的文字已经说明，可能你忽略了，请重读一遍。

G-Spider

28# fly

因为随机值不存在依赖关系，不好利用之前的结果。
如果说是生产0~n之间的随机数，然后生成一个比n小的素数，可以
适当的缩小一下随机数范围到0~m   (m<n)  ，这样可以保证一遍成功。