素性测试

Miller Rabin

片段

bool miller_rabin(i64 n) {
	if (!is_prime_small(n))
		return false;
	i64 a = n - 1;
	a /= a & -a;
	for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
		if (n <= p)
			return true;
		i64 t = a, v = qpow64(p, t, n);
		while (t != n - 1 && v != 1 && v != n - 1)
			v = i128(v) * v % n, t *= 2;
		if (v != n - 1 && t % 2 == 0)
			return false;
	}
	return true;
}

EXPAND

using i128 = __int128_t;

i64 qpow64(i64 a, i64 n, i64 m) {
 i64 ret = 1 % m;
 for (; n; n /= 2) {
  if (n & 1)
   ret = i128(a) * ret % m;
  a = i128(a) * a % m;
 }
 return ret;
}

bool is_prime_small(i64 n) {
 if (n < 64)
  return (0x28208a20a08a28ac >> n) & 1;
 if ((0xdf75d77d >> (n % 30)) & 1)
  return false;
 if (n % 7 == 0 || n % 11 == 0)
  return false;
 return true;
}

bool miller_rabin(i64 n) {
 if (!is_prime_small(n))
  return false;
 i64 a = n - 1;
 a /= a & -a;
 for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
  if (n <= p)
   return true;
  i64 t = a, v = qpow64(p, t, n);
  while (t != n - 1 && v != 1 && v != n - 1)
   v = i128(v) * v % n, t *= 2;
  if (v != n - 1 && t % 2 == 0)
   return false;
 }
 return true;
}