首页 > 编程语言 > 详细

Miller_Rabin算法(随机算法,判断一个数是否是素数)

时间:2017-02-23 22:49:10      阅读:328      评论:0      收藏:0      [点我收藏+]
 1 const int S = 20;//随机算法判定次数,S越大,判错概率越小
 2 LL pow_mod(LL a, LL b, LL mod) { // a^b%mod
 3     LL ans = 1;
 4     a = a % mod;
 5     while(b) {
 6         if(b & 1) {
 7             ans = (ans * a) % mod;
 8         }
 9         a = ( a * a ) % mod;
10         b >>= 1;
11     }
12     return ans;
13 }
14 bool check(LL a, LL n, LL x, LL t) {
15     LL ret = pow_mod(a, x, n);
16     LL last = ret;
17     for(int i = 1; i <= t; i++) {
18         ret = (ret * ret) % n;
19         if(ret == 1 && last != 1 && last != n - 1) return true;
20         last = ret;
21     }
22     if(ret != 1) return true;
23     else return false;
24 }
25 bool Miller_Rabin(long long n) {
26     if(n < 2)return false;
27     if(n == 2) return true;
28     if( (n & 1) == 0) return false;
29     LL x = n - 1;
30     LL t = 0;
31     while( (x & 1) == 0 ) {
32         x >>= 1;
33         t++;
34     }
35     for(int i = 0; i < S; i++) {
36         LL a = rand() % (n - 1) + 1;
37         if(check(a, n, x, t))
38             return false;
39     }
40     return true;
41 }

 

Miller_Rabin算法(随机算法,判断一个数是否是素数)

原文:http://www.cnblogs.com/27sx/p/6435905.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!