关于大数的问题

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，不是素数

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

复制代码

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

仰望天上的光

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

wangyexin

伪素数原理