밀러–라빈 소수 판정법 (Miller

밀러–라빈 소수 판정법 (Miller–Rabin)

RSA 키를 만들려면 수백 자리 소수가 필요하다. 그런데 에라토스테네스의 체나 "2부터 √n까지 나눠 보기"는 이런 크기에서는 우주가 끝날 때까지 돌려도 안 끝난다. 그래서 실전에서는 확률적 소수 판정을 쓴다 — 완벽히 증명하지는 않지만, 몇 번만 검사해도 틀릴 확률을 사실상 0으로 만들 수 있다. 밀러–라빈은 그중 가장 널리 쓰이는 방법으로, OpenSSL·Python·GnuPG의 키 생성 코드 안에서 지금도 돌고 있다.

1. 출발점: 페르마의 소정리

p 가 소수이고 1 ≤ a < p 이면 항상 다음이 성립한다.

a^p−1 ≡ 1 (mod p)

그러니 어떤 a 로 aⁿ⁻¹ mod n ≠ 1 이 나오면 n 은 확실히 합성수다 (이때 a 를 "증인(witness)"이라 부른다). 하지만 이 페르마 판정에는 구멍이 있다 — 카마이클 수(561, 1105, 1729…)는 소수가 아닌데도 거의 모든 a 에 대해 aⁿ⁻¹ ≡ 1 을 통과해 버린다. 밀러–라빈은 이 구멍을 제곱근 검사로 막는다.

2. 핵심 아이디어: 1의 "비자명한" 제곱근 잡기

n 이 소수이면 방정식 x² ≡ 1 (mod n) 의 해는 x ≡ 1 과 x ≡ n−1(= −1) 딱 두 개뿐이다. 만약 ±1 이 아닌 어떤 수를 제곱했더니 1 이 되면, 그건 n 이 합성수라는 결정적 증거다.

먼저 짝수인 n−1 에서 2를 최대한 뽑아내 n − 1 = 2^s · d 로 쓴다 (d 는 홀수). 그다음 a^d mod n 부터 시작해 계속 제곱하며 수열을 만든다:

a^d, a^2d, a^4d, … , a^{2^s−1·d} (mod n)

n 이 소수라면 이 수열은 반드시 다음 중 하나다 — ① 맨 처음부터 1 이거나, ② 어느 지점에서 n−1 이 나온 뒤 1 로 떨어진다. 둘 다 아니면(예: 1 앞에 −1 없이 다른 수가 있으면) a 는 합성수 증인이고 판정은 즉시 "합성수"로 끝난다.

3. 직접 판정해 보기

라운드 k

97 (소수) 561 (카마이클 수) 1105 (카마이클 수) 2047 (밑 2의 강한 유사소수) 3215031751 (밑 2·3·5·7 유사소수) 2147483647 (메르센 소수 2³¹−1) 1000000007 (경시대회 소수)

※ 데모는 BigInt 로 계산하므로 큰 수도 정확하다. 밑 a 는 2 … n−2 에서 무작위로 뽑는다 (같은 수라도 실행마다 뽑히는 밑이 달라 표가 바뀔 수 있다).

4. 왜 "확률적"인데 믿을 수 있나

핵심 정리: 합성수 n 에 대해, 2 … n−2 중 무작위로 고른 밑 a 가 "거짓 증인"일 확률은 최대 1/4 이다 (실제로는 훨씬 작다). 밑을 독립적으로 k번 뽑아 모두 통과하면 n 이 합성수인데도 못 걸러낼 확률은 (1/4)^k 이하로 급격히 줄어든다.

k=10 → 오판 확률 ≤ 1/1,000,000
k=20 → ≤ 1조 분의 1 (하드웨어 오류 확률보다 낮음)
소수를 합성수로 잘못 볼 일은 절대 없다 — "합성수" 판정은 항상 옳다

작은 수라면 결정론적으로도 쓸 수 있다. 특정 밑 집합만 검사하면 그 범위 안에서는 100% 정확하다.

a ∈ {2, 3} → n < 1,373,653 까지 확정
a ∈ {2,3,5,7,11,13,17,19,23,29,31,37} → n < 3.3 × 10²⁴ (64비트 전 범위) 확정
암호용 대형 소수는 범위 표가 없으므로 무작위 k라운드를 쓴다

5. 코드로 보기

def is_probable_prime(n, k=20):
    if n < 2: return False
    for p in (2,3,5,7,11,13):        # 작은 소수 빠른 처리
        if n % p == 0: return n == p

    # n - 1 = 2^s * d  (d 는 홀수)
    s, d = 0, n - 1
    while d % 2 == 0:
        d //= 2; s += 1

    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)              # a^d mod n  (빠른 거듭제곱)
        if x == 1 or x == n - 1:
            continue                    # 이 밑은 통과
        for _ in range(s - 1):
            x = x * x % n              # 제곱해 나간다
            if x == n - 1:
                break
        else:
            return False               # -1 을 못 만남 → 합성수 확정
    return True                      # k 라운드 모두 통과 → 거의 확실히 소수

비용은 라운드마다 a^d mod n 한 번(빠른 거듭제곱 O(log n) 곱셈)과 최대 s 번의 제곱뿐이다. 수천 자리 수도 순식간에 판정된다. Python 3.8+ 의 sympy.isprime, Java BigInteger.isProbablePrime, Miller–Rabin + Lucas 를 섞은 BPSW 판정이 모두 이 골격을 공유한다.

6. 한 줄 요약

페르마 판정에 "1의 제곱근은 ±1뿐" 이라는 소수의 성질을 더한 것이 밀러–라빈이다. 무작위 밑을 k번 던져 하나라도 걸리면 합성수 확정, 다 통과하면 오판 확률 (1/4)^k 이하로 소수. 빠르고, 카마이클 수에 안 속고, 현대 암호가 의존하는 판정법이다.