[소수 판정] 밀러-라빈 알고리즘 (Miller-Rabin primality test)

페르마의 소정리(https://uneducatedjungler.tistory.com/120)에서 이어지는 글

 

n이 소수라면 (n의 배수가 아닌) 모든 a에 대해 위 식을 만족한다는 것이 페르마의 소정리이다.

 

즉, 어떤 단 하나의 a에 대해서라도 위 식을 만족하지 못함이 발견된다면, p는 100% 소수가 아니게 된다.

이에 확률론적으로 접근하면, p가 많은 수의 a에 대해 위 식을 만족할수록 p가 소수일 확률이 높아진다.

 

페르마 계열의 소수판별법은 여럿이 있는데, 요약하면 다음과 같다.

 

n이 소수라면 위 식을 만족할테니, 충분히 많은 아무 a나 넣어보며 위 식을 만족하는지 확인하자.

한번이라도 만족을 안함이 발견되면 n은 소수가 아니다. break and return False

테스트를 다 통과하면 p는 '아마도 소수'다. return True

 

이때 소수인지 알고싶은 n은 당연히 홀수일 것이고, 아마도 매우 클 것이다.

이런 n에 대해 a^(n-1)의 모듈러 연산을 직접 하는 것은 연산력의 낭비가 되므로, 약간의 전처리를 거친다.

n-1은 짝수부 2^s과 남은 홀수 d의 곱으로 표현할 수 있다.

그렇다면, 맨 위의 식은 아래와 같이 표현될 수 있다.

 a^(n-1)이 1이라면 a^d가 1이라 이것을 여러번 곱해 1이 된 경우거나, s보다 작은 어떤 r에 대해 a^(2^rd)가 -1이라서 이것을 짝수번 곱해 1이 된 경우라는 의미이다.

즉, 여러 a에 대해 n이 이 두 식 중 하나를 만족하는지 찔러보는 것이 밀러 라빈 소수판별법이다.

 

def MillerRabin(n) : 
    alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    if n in alist : 
        return True
    if n < 2 or n % 2 == 0 : 
        return False
    if n < 1373653 : 
        alist = [2, 3]
    elif n < 9080191 : 
        alist = [31, 73]
    elif n < 4759123141 : 
        alist = [2, 7, 61]
    elif n < 2152302898747 : 
        alist = [2, 3, 5, 7, 11]
    elif n < 3474749660383 : 
        alist = [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321 : 
        alist = [2, 3, 5, 7, 11, 13, 17]
    
    d = n - 1
    s = 0
    while d % 2 == 0 : 
        d = d // 2
        s = s + 1
    for a in alist : 
        x = pow(a, d, n)
        if x == 1 : 
            continue
        stest = False
        for i in range(s) : 
            if x == n - 1 : 
                stest = True
                break
            x = pow(x, 2, n)
        if not stest : 
            return False
    return True

밀러 라빈 소수판별법은 원칙적으로는 100% 소수라고 확정할 수가 없는 확률적 알고리즘이다.

line 2의 alist에 랜덤한 a를 많이 넣을수록 소수일 확률이 높아지는 셈.

하지만 여러 수학자들의 연구 덕에 충분히 작은 수 (n<341550071728321)의 경우에는 특정한 몇몇 a에 대해서만 확인해보면 100% 소수임을 장담할 수 있다. 예를 들어 n이 1373653 이하면 a = 2, 3의 두번만 넣어봐도 소수인지 아닌지 알 수 있다는 것이다. (위키피디아 참고, line 7 ~ 18)

즉 우리가 PS 등에서 일반적으로 접할 1e15 이하의 작은 수의 소수판별에서는 빠르게 결정론적으로 소수판별이 가능한 강력한 알고리즘이 된다.

 

밀러-라빈 소수판별법을 PS에 응용해서 풀 수 있는 문제의 예는 다음과 같다.

5615 아파트 임대 https://www.acmicpc.net/problem/5615

거의 대부분의 소수 판정 문제 https://www.acmicpc.net/problemset?sort=ac_desc&algo=9

 

PS는 소수판별 자체가 메인이 되는 문제보다는 소인수분해 등의 응용이 많다보니, 이것만 안다고 해서 바로 풀리는 고난도 문제는 그리 많지 않은 것 같다. 대신 열 자리수 이상의 큰 수를 소인수분해해야하는 종류의 문제에서, n이 소수인지 아닌지 아는 것만으로도 다뤄야할 자릿수가 절반이 되니(소수가 아니라면 적어도 두 소수의 곱이니까) 문제해결에 큰 도움이 된다.

 

특히, 난수 충돌을 이용하여 n의 임의의 인수(소인수가 아닐 수 있음)를 리턴하는 폴라드 로 알고리즘과 같이 이용하면, 폴라드 로의 리턴값에 밀러 라빈을 이용해 소수인지 판정하는 것으로 소인수를 비교적 빠른 시간 안에 추출할 수 있다.