素性测试算法 Miller-Rabin

  时间:2020-08-03 11:54:11  阅读量:29  评论数:0  作者:ylxmf2005

该篇文章素性测试算法Miller-Rabin除了讲述概念知识,更举例源码分析教学,对这方面技术有需求的朋友可以参考着学习,实用性较强。

费马小定理

pp 为质数, aa 为任意自然数, 则
apa(modp)    ap11(modp)a^{p} \equiv a\pmod p \iff a^{p-1} \equiv 1 \pmod p

证明略。

二次探测定理

pp 为质数,则 x21(modp)x^2 \equiv 1 \pmod p 的解为 x1=1,x2=p1x_1 = 1, x_2 = p-1

略证:

x21(modp)x210(modp)(x 1)(x1)0(modp)p(x1)×(x 1) x^2 \equiv 1 \pmod p \\ x^2 - 1 \equiv 0 \pmod p \\ (x 1)(x-1) \equiv 0 \pmod p \\ p | (x - 1)\times (x 1)

Miller-Rabin

我们都知道,如果 pp 为质数那么有 ap11(modp)a^{p-1} \equiv 1 \pmod p。但反命题不一定成立,比如令 a=2a=2,那么有 2340mod341=12^{340} \bmod 341 = 1,但是 341=11×31341 = 11 \times 31。那么再试一下 a=3a=3,发现 3340mod341=563^{340} \bmod 341 = 56,所以 341341 不是质数。

那么能不能多选几个质数去做检测呢?但是有一些合数,叫做 Carmichael 数,比如 561=3×11×17561 = 3\times11 \times17,所有合法的底数都无法将它检测出来。

那么接下来就是正题了——Miller-Rabin 素性测试算法。先拿 341341 举个栗子,看看这个算法在干什么。

先说明一个显而易见的命题,对于任意质数 pp2p12| p -1。那么看看 Miller-Rabin 干了什么。

因为 23401(mod341)2^{340} \equiv 1 \pmod {341},那么有217021(mod341)2^{{170}^2} \equiv 1 \pmod {341},若将 21702^{170} 看作一个整体,根据二次探测定理,如果 341341 是一个质数,那么 2170mod341=1/3402^{170} \bmod 341 = 1 / 340。可以发现 2170mod3412^{170} \bmod 34111。那么还适用二次探测定理,再看看 285mod3412^{85} \bmod 341,发现它为 3232,所以 341341 不是质数。

int ksm(int a, int k, int p) {
  	int res = 1;
  	while (k) {
    	if (k & 1) res = res * a % p;
    	a = a * a % p;
    	k >>= 1;
  	}
  	return res % p;
}
int MR(int x, int p) {
	if (ksm(x, p-1, p) != 1) return 0;
	int k = p - 1;
	while (!k & 1) {
		k >>= 1;
		int t = ksm(x, k, p);
		if (t == p - 1) return 1;
		if (t != 1) return 0;
	}
	return 1;
}
int RP(int p) {
	if (p == 2 || p == 3 || p == 5 || p == 7 || p == 11) return 1;
	if (p == 0) return 0;
	return MR(2, p) && MR(3, p) && MR(5, p) && MR(7, p) && MR(11, p);
}
int main() {
	while (1) {
		int x = read();
		printf("%d\n", RP(x));
	}
	return 0;
}

可以发现 Miller-Rabin 的时间按复杂度为 O(klog2n)O(k \log^2 n),其中 kk 为测试次数,通常五次就够了。

关键词:素性测试,测试,算法