Miller Rabbin算法

前言

这是一个判断大整数是否是质数的算法

讲解

我们如何判断一个数(n)是否是质数？首先我们肯定想到的是暴力找因数，时间复杂度为(O(sqrt n))

但是当(n)达到(10^{18})级别时，这个看似优秀的时间复杂度也行不通了

这时候我们就需要Miller Rabbin算法！

首先我们根据费马小定理可知(a^{p-1} ≡ 1 pmod p)，其中(p)是质数

如果对于一个(p mid a)，(p)满足上述条件，则有可能是质数，否则一定不是质数

因为有一类数虽然不是质数但也可能满足这个条件，但是如果我们取多个(a)判断，失误的概率就会变得很小很小

在此基础上，为了让其更为准确，我们可以使用二次探测

假如(p-1=k*2^t，x=k*2^{t-1},x^2=p-1)

(ecause a^{p-1} ≡ 1 pmod p)

( herefore a^{x^2} - 1 ≡ 0 pmod p)

( herefore (a^x+1)(a^x-1) ≡ 0 pmod p)

( herefore a^x ≡ 1 pmod p)或者(a^x ≡ p-1 pmod p)

如果不满足这个条件，(p)就一定不是质数，因为当且仅当(p)为合数时(a^x)才可能既不是(1)也不是(p-1)

反向倒推(a^x)太过麻烦，我们可以先求出(a^{k})，对其进行平方，操作(t)次

如果现在的值为(1)，前一次的值如果不是(p-1)，则一定不是质数，否则认为它通过此次测试

代码

warning!板子似乎出了一些意料之外的错误！

bool vis[MAXN];
int prime[MAXN],pn;

void sieve(int x)
{
	for(int i = 2;i <= x;++ i)
	{
		if(!vis[i]) prime[++pn] = i;
		for(int j = 1;j <= pn && i * prime[j] <= x;++ j)
		{
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
LL gsc(LL x,LL y,LL MOD)
{
	LL ret = 0;
	while(y){if(y & 1) ret = (ret + x) % MOD;x = (x << 1) % MOD;y >>= 1;}
	return ret;
}
LL qpow(LL x,LL y,LL MOD)
{
	x %= MOD;
	LL ret = 1;
	while(y){if(y & 1) ret = gsc(ret,x,MOD);x = gsc(x,x,MOD);y >>= 1;}
	return ret;
}
bool mr(LL x,LL p)
{
	LL k = p-1,t = 0;
	while(!(k&1)) k >>= 1,t++;
	LL now = qpow(x,k,p);
	if(now == 1) return 1;
	while(t--)
	{
		LL lst = now;
		now = gsc(now,now,p); 
		if(now == 1)
		{
			if(lst != p-1) return 0;
			return 1;
		}
	}
	return 0;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	sieve(100);
	while(~scanf("%I64d",&n))
	{
		if(n <= 100)
		{
			if(vis[n]) printf("It is not a prime number.
");
			else printf("It is a prime number.
");
			continue;
		}
		bool f = 1;
		for(int i = 1;i <= pn;++ i)
			if(!mr(prime[i],n))
			{
				f = 0;
				break;
			}
		if(f) printf("It is a prime number.
");
		else printf("It is not a prime number.
");
	}
	return 0;
}