关于大数的问题

bevin

以前看过算法判断大数是否为素数的问题，不过现在忘了。。。。哪位能提供下思路，不胜感激~~~~~~~

soldier

Rabin -Miller算法是典型的验证一个数字是否为素数的方法。判断素数的方法是Rabin-Miller概率测试，那么他具体的流程是什么呢。假设我们要判断n是不是素数，首先我们必须保证n 是个奇数，那么我们就可以把n 表示为 n = (2^r)*s+1,注意s 也必须是一个奇数。然后我们就要选择一个随机的整数a (1<=a<=n-1)，接下来我们就是要判断 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我们就说n通过了测试，但是有可能不是素数也能通过测试。所以我们通常要做多次这样的测试，以确保我们得到的是一个素数。（DDS的标准是要经过50次测试）
采用Rabin-Miller算法进行验算
首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
（1） 选择一个小于p的随机数a。
（2） 设j=0且z=a^m mod p
（3） 如果z=1或z=p-1，那麽p通过测试，可能使素数
（4） 如果j>0且z=1, 那麽p不是素数
（5） 设j=j+1。如果j且z<>p-1,设z=z^2 mod p，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。
（6） 如果j=b 且z<>p-1，不是素数

01.#include<iostream.h> 
02.#include<time.h> 
03.#include<stdlib.h> 
04. 
05.//随机数产生器 
06.//产生m~n之间的一个随机数 
07.unsigned long random(unsigned long m,unsigned long n) 
08.{ 
09. srand((unsigned long)time(NULL)); 
10. return(unsigned long)(m+rand()%n); 
11.} 
12.//模幂函数 
13.//返回X^YmodN 
14.long PowMod(long x,long y,long n) 
15.{ 
16. long s,t,u; 
17. 
18. s=1;t=x;u=y; 
19. while(u){ 
20. if(u&1)s=(s*t)%n; 
21. u>>=1; 
22. t=(t*t)%n; 
23. } 
24. return s; 
25.} 
26. 
27. 
28.//Rabin-Miller素数测试，通过测试返回1，否则返回0。 
29.//n是待测素数。 
30.//注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4 
31. 
32.int RabinMillerKnl(unsigned long n) 
33.{ 
34. unsigned long b,m,j,v,i; 
35. //先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数 
36. m=n-1; 
37. j=0; 
38. while(!(m&1)) 
39. { 
40. ++j; 
41. m>>=1; 
42. } 
43. //随机取一个b，2<=b<n-1 
44. b=random(2,m); 
45. //计算v=b^mmodn 
46. v=PowMod(b,m,n); 
47. //如果v==1，通过测试 
48. if(v==1) 
49. { 
50. return 1; 
51. } 
52. 
53. i=1; 
54. //如果v=n-1，通过测试 
55. while(v!=n-1) 
56. { 
57. //如果i==l，非素数，结束 
58. if(i==j) 
59. { 
60. return 0; 
61. } 
62. //v=v^2modn，i=i+1 
63. v=PowMod(v,2,n); 
64. i++; 
65. } 
66. return 1; 
67.} 
68.intmain() 
69.{ 
70. unsigned long p; 
71. int count=0; 
72. cout<<"请输入一个数字"<<endl; 
73. cin>>p; 
74. for(int temp=0;temp<5;temp++) 
75. { 
76. if(RabinMillerKnl(p)) 
77. { 
78. count++; 
79. } 
80. else 
81. break; 
82. 
83. } 
84. 
85. if(count==5) 
86. cout<<"一共通过5次测试，是素数！"<<endl; 
87. else 
88. cout<<"不是素数"<<endl; 
89. return 0; 
90.} 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/aichaoguy/archive/2010/12/04/6054915.aspx

仰望天上的光

LZ也可以baidu下“筛法求素数”

wangyexin

伪素数原理