밀러 - 라빈 소수 판정법

소수 판정법 이해에 필요한 기초 지식이다. 해당 판정법은 페르마의 소정리에 기반을 둔다. $p$는 홀수인 소수이고, $a$는 양의 정수이다.
페르마의 소정리 2)에 의해 $a^{p-1}=a^{2^{s}\times d}\equiv1(mod\ p)$가 성립한다. 우변의 1을 좌변으로 넘긴 후 전개하면 다음과 같다.

$a^{2^{s}\times d}-1$를 다음과 같이 변형할 수 있다.

$a^{2^{s}\times d}-1$의 각 인수가 $p$에 의해 나누어 떨어진다면, 즉 $a^{2^{s-1}\times d}$, $a^{2^{s-2}\times d} \cdots$ 등을 $p$로 나누었을 때의 나머지가 -1이라면 $p$는 아마 소수일 것이다. 마지막 항$(a^{d} - 1)$의 경우, 나머지가 1이라면 $p$는 아마 소수일 것이다.

구현은 생각보다 간단하다.

def miller_rabin(a, p):
    k = p - 1
    while True:
        tmp = power_mod(a, k, p) # a^(p-1) % p
        if tmp == p - 1: # a^(k) % p == -1
            return True
        k //= 2 # a^(s-1), a^(s-2)... 
        if k % 2 == 1: # k가 홀수라면, 즉 2^s * d에서 d만 남았다면
            break
    # (a^d + 1)(a^d - 1)만 남아 있음.
    return (tmp == p - 1 or tmp == 1)

int 범위의 경우, $a$에 2, 7, 61을, long long의 경우 37 이하의 모든 소수에 대해 위의 구현이 성립한다면 $p$는 소수임이 증명되었다고 한다.