밀러-라빈 소수 판별법

밀러-라빈 소수 판별법(Miller-Rabin Primality Test)이란?

밀러 라빈 소수 판별법은 $O(\log^3 n)$의 시간복잡도를 가지는 확률적으로 n이 소수인지 아닌지 판단하는 알고리즘입니다.

페르마의 소정리에서 $p$가 2가 아닌 소수일 때

$a^{p-1}\equiv 1\pmod{p}$

이고, $p$는 소수이기 때문에 어떠한 홀수 $d$에 대해서 $p-1 = d\times2^{s}$ 로 표현할 수 있습니다.

또

$x^2 \equiv 1\pmod{p}$ 라면
$x \equiv -1 \quad or \quad x \equiv 1\pmod{p}$

이기 때문에, 어떤 2가 아닌 소수 $n$에 대해서

$a^{n-1} \equiv 1\pmod{n}$
$a^{d\times2^s} \equiv 1\pmod{n}$ 양변에 제곱을 해주면
$(a^{d\times2^s})^2 \equiv 1\pmod{n}$
$a^{d\times2^{s-1}}\equiv-1\quad or \quad a^{d\times2^{s-1}}=1\pmod{n}$
만약 $a^{d\times2^{s-1}}\equiv1\pmod{n}$ 이라면 위와 같은 과정을 반복해서
$a^d \equiv 1\quad or\quad a^d \equiv -1\pmod{n}$ 으로 만들 수 있습니다.

정리해보면, $n$보다 작은 양의 정수 $a$에 대해서

$a^d\equiv1\pmod{n}$
$a^{d\times2^r}\equiv-1\pmod{n} \; for\; some \;r\; (0\le r\le s)$

중 하나가 성립한다면 $n$은 소수일것이라고 말할 수 있습니다.

코드

miller_rabin = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

def power(base, exponent, mod): # 분할 정복을 이용한 거듭제곱
    res = 1

    base %= mod
    while exponent > 0:
        if exponent % 2 == 1:
            res = res * base % mod
        exponent = exponent // 2
        base = (base * base) % mod
    return res


def m_r(n, a): 
    d = n - 1
    while d % 2 == 0:
        d //= 2 # n - 1 = 2**s*d
    x = power(a, d, n) # a**d (mod n)
    if x == 1 or x == n - 1: # 위가 1 혹은 mod n이 -1이라면
        return True
    while d != n - 1: # 제곱을 해주면서 2**s가 될때까지
        x = power(x, 2, n)
        d *= 2
        if x == n - 1: # a**{d*2**r}=-1(mod n)이면 True
            return True
    return False
    
def isPrime(n):
    if n in miller_rabin:
        return True

    if n == 1 or n % 2 == 0:
        return False

    for i in miller_rabin:
        if not m_r(n, i):
            return False

    return True