Miller_Rabin 学习笔记

费马小定理：对于任意一个质数满足：\(a^{p-1}\equiv1\pmod p\)

二次探测：对于任意一个奇质数满足：\(x^2\equiv1\pmod p\) 的解为 \(x=1\) 或 \(x=p-1\)

将两个定理结合起来，设 \(p-1=u\times 2^t\)，那么计算出 \(a^u\) 次方后不断进行平方计算，如果某次平方后得到了 1 并且平方的数不为 \(1\) 或 \(p-1\)，那么 \(p\) 肯定不是质数。

据说 \(a\) 选取前 13 个质数就行了，也可以使用下面程序给的数字列表。注意特判偶数和小于 3 的情况

int prime(LL n)
{
	if(n<3||n%2==0)
		return n==2;
	LL t=n-1;
	int s=0;
	while(!(t&1))
		t>>=1,s++;
	static const int pr[]={2,325,9375,28178,450775,9780504,1795265022};
	for(int i=0;i<7;i++)
	{
		int x=pr[i];
		LL v=pown(x,t,n);
		if(v==1||!v||v+1==n)
			continue;
		for(int j=1;j<=s;j++)
		{
			v=(LLL)v*v%n;
			if(j^s&&v==n-1)
			{
				v=1;
				break; 
			}
			if(v==1)
				return 0;
		}
		if(v^1)
			return 0;
	}
	return 1;
}
···