Miller-Rabin primality test

Assume that we are asked if \(n\) is a prime.

Fermat primality test: choose some numbers \(a_1,a_2,\cdots,a_x<n\) and check if \(\forall i,a_i^{n-1}\equiv 1\pmod n\).

However, this may get wrong answer on some special numbers such as \(561\).

Here is a theorem: if \(p\) is an odd prime, there are only two solutions of \(x^2\equiv 1\pmod p\), one is \(x\equiv 1\), the other is \(x\equiv p-1\).

Prove: the equation can be transformed into \((x+1)(x-1)\equiv 0\). Since \(p\) is an odd prime, you cannot find two positive integers less than \(p\) of which product is a multiple of \(p\), aka. either \(x+1\equiv 0\) or \(x-1\equiv 0\) is true.

So, If you find a \(x\) satisfying \(x^2\equiv 1\pmod n\) and \(x\not\equiv\pm 1\pmod n\), \(n\) cannot be a prime.

Miller-Rabin primality test performs both the above-mentioned process and Fermat primality test to determine whether \(n\) is a prime.

First, find the biggest integer \(t\) makes \(n-1=u\cdot 2^t\) (\(u\) is a integer). Then test several times, each time choose a integer \(a\) which is smaller than \(n\). Let \(v\) be \(a^u\bmod n\). Transform \(v\) into \(v^2\bmod n\) for \(t\) times. If \(n\) is an odd prime, either \(v\) is \(1\) at first or there is a moment \(v=n-1\).

typedef long long ll;
bool isPrime(ll n){
	if((n&1)^1)return n==2;
	ll u=n-1;int t=0;
	while((u&1)^1)u>>=1,t++;
	for(ll a:TestBase){
		a%=n;ll v=fpow(a,u,n);
		if(v==1||a==0)continue;
		int k=0;for(;k<t;k++){
			if(v==n-1)break;
			v=(__int128)v*v%n;
		}
		if(k==t)return 0;
	}
	return 1;
}

If you choose the first \(12\) primes as \(a\) and \(n\in[1,2^{64})\), it can absolutely determine whether \(n\) is a prime.