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;
}