밀러라빈

using ll = long long;
inline ll multiply(ll a, ll b, ll mod) { return __int128(a) * b % mod; }
ll power(ll a, ll n, ll mod) { //a ^ n % mod
    ll res = 1;
    while (n) {
        if (n & 1) res = multiply(res, a, mod);
        a = multiply(a, a, mod);
        n >>= 1;
    }
    return res;
}
bool isPrime(ll n) {
    if (n <= 1) return false;
    ll d = n - 1, r = 0;
    while (~d & 1) d >>= 1, ++r;
    auto check = [&](ll a) {
        ll remain = power(a, d, n);
        if (remain == 1 || remain == n - 1) return true;
        for (int i = 1; i < r; i++) {
            remain = multiply(remain, remain, n);
            if (remain == n - 1) return true;
        }
        return false;
    };
    vector<ll> nums = {2,325, 9375, 28178, 450775, 9780504, 1795265022};
    for (ll a : nums) if (a % n && !check(a)) return false;
    return true;
}

$N$이 소수이면 $\rightarrow$ proposition p
$a^{N-1}\equiv1 \pmod{N} (\because \text{Fermat’s little theorem}$)
let) $N - 1 = d \times 2^r, d \equiv 1 \pmod{2}$
$a^{d \times 2^r} \equiv 1\pmod{N}$
$a^{d \times 2^{r-1}} \equiv \pm1\pmod{N}$
$a^{d \times 2^{r-1}} \equiv +1\pmod{N}$ 인 경우에 대해 재귀적으로 $\pm1$로 분해하면
$\therefore a^{d} \equiv \pm1\pmod{N}$ or $a^{d \times 2^i} \equiv -1 \pmod{N}$ $\rightarrow$ proposition q

p -> q 의 대우 ~q -> ~p 를 사용.

즉, q를 만족하지 않으면 반드시 합성수.

역은 성립하지 않기에 q를 만족한다고 해서 소수인 건 아님.

하지만 unsigned long long 범위의 모든 수는 $a \in \{2,325, 9375, 28178, 450775, 9780504, 1795265022\}$ 7가지 경우에 대해 걸러지지 않았다면 소수라는 게 알려짐
int 범위는 {2, 7, 61}만으로도 충분