avatar

Miller-Rabin 素性测试代码

Miller-Rabin 素性测试代码

  • 之前的笔记中讲过这个算法,所以在这里把代码贴一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int prime[8] = {2, 3, 5, 8, 11, 13, 17, 37};

bool miller_rabin(int n, int a) {
int d = n - 1, r = 0;
while(d % 2 == 0)
d = d >> 1, r++;
int z = fastPower(a, d, n);
if(z == 1) return true;
for(int i = 0; i < r; i++) {
if(z == n - 1) return true;
z = 1ll * z * z % n;
}
return false;
}

bool check(int n) {
if(n < 2) return false;
for(int i = 0; i < 8; i++) {
if(n == prime[i]) return true;
if(n % prime[i] == 0) return false;
if(!miller_rabin(n, prime[i])) return false;
}
return true;
}
文章作者: Ender
文章链接: https://www.ender.xin/post/6b2f3ed1.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论