米勒罗宾素数测试

2020-03-07

字数统计: 334字 | 阅读时长≈ 1分钟

米勒罗宾素数测试的总结

模板

1	复制// 18位素数：154590409516822759
2	// 19位素数：2305843009213693951 (梅森素数)
3	// 19位素数：4384957924686954497
4	LL prime[6] = {2, 3, 5, 233, 331};
5	LL qmul(LL x, LL y, LL mod) { // 乘法防止溢出，如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法
6
7
8	return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
9	/*
10	LL ret = 0;
11	while(y) {
12	if(y & 1)
13	ret = (ret + x) % mod;
14	x = x * 2 % mod;
15	y >>= 1;
16	}
17	return ret;
18	*/
19	}
20	LL qpow(LL a, LL n, LL mod) {
21	LL ret = 1;
22	while(n) {
23	if(n & 1) ret = qmul(ret, a, mod);
24	a = qmul(a, a, mod);
25	n >>= 1;
26	}
27	return ret;
28	}
29	bool Miller_Rabin(LL p) {
30	if(p < 2) return 0;
31	if(p != 2 && p % 2 == 0) return 0;
32	LL s = p - 1;
33	while(! (s & 1)) s >>= 1;
34	for(int i = 0; i < 5; ++i) {
35	if(p == prime[i]) return 1;
36	LL t = s, m = qpow(prime[i], s, p);
37	while(t != p - 1 && m != 1 && m != p - 1) {
38	m = qmul(m, m, p);
39	t <<= 1;
40	}
41	if(m != p - 1 && !(t & 1)) return 0;
42	}
43	return 1;
44	}