MillerRabin

Deterministic Miller-Rabin primality test. Guaranteed to work for numbers up to 7 · 10^18; for larger numbers, use Python and extend A randomly.

Time: 7 times the complexity of a^b mod c. 12 lines Stress-tested

Needs: "ModMulLL.h"

content/number-theory/MillerRabin.h — chilli, c1729, Simon Lindholm, source: Wikipedia, https://miller-rabin.appspot.com/

bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
	    s = __builtin_ctzll(n-1), d = n >> s;
	for (ull a : A) {   // ^ count trailing zeroes
		ull p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}