Computer >> 컴퓨터 >  >> 프로그래밍 >> 프로그래밍

밀러-라빈(Miller-Rabin) 소수 판별 알고리즘의 원리와 예제 완벽 정리

밀러-라빈(Miller-Rabin) 소수 판별 알고리즘이란?

밀러-라빈(Miller-Rabin) 알고리즘은 아주 큰 수의 소수(prime) 여부를 빠르게 검사하는 확률적 방법입니다. 라빈-밀러(Rabin-Miller) 소수성 검정이라고도 불리며, 페르마(Fermat) 소수성 검정이나 솔로베이-스트라센(Solovay-Strassen) 검정과 같은 계열에 속하는 알고리즘입니다.

이 검정의 기본 원리는 간단합니다. “진짜 소수라면 반드시 성립하는 등식(들)”을 먼저 정의한 뒤, 소수인지 검사하려는 수가 그 등식을 만족하는지 확인하는 것입니다. 만족하지 않는다면 그 수는 소수가 아닙니다.

밀러-라빈은 지금까지 알려진 소수 판별 알고리즘 중 가장 실용적으로 널리 쓰이는 방법으로, RSA 암호화 기반의 각종 소프트웨어 라이브러리에서 활용됩니다. 대표적인 사례가 바로 OpenSSL입니다.

흥미로운 점은, 밀러-라빈 검정이 어떤 수가 합성수(composite)임을 확실하게 증명할 수 있다는 사실입니다. 그래서 엄밀히 말하면 이 검정은 ‘소수성 검정’이라기보다 ‘합성수 검정’에 가깝습니다. 모든 합성수 n에 대해 적어도 3/4의 밑(base) a가 n의 합성수임을 밝혀주는 증거(witness) 역할을 하기 때문입니다.

또한 밀러-라빈은 페르마의 소정리(Fermat's Little Theorem)를 단순하게 확장한 형태로, 페르마의 소정리만 사용할 때보다 훨씬 높은 신뢰도로 소수 여부를 판별할 수 있습니다.

알고리즘: 의사 코드(Pseudocode)

MILLER-RABIN-TEST(n, a)   // n: 검사할 수, a: 밑(base)
{
    // n − 1 = m × 2^k 를 만족하는 m(홀수)과 k를 찾는다
    T ← a^m mod n
    if (T = 1 또는 T = n − 1) return “아마도 소수”
    for (i ← 1 to k − 1)        // 최대 k − 1단계 반복
    {
        T ← T² mod n
        if (T = n − 1) return “아마도 소수”
        if (T = 1)     return “합성수”
    }
    return “합성수”
}

오류 확률

어떤 수가 밀러-라빈 검정을 한 번 통과했을 때, 그 수가 실제로는 합성수일 확률은 최대 1/4임이 증명되어 있습니다. 서로 다른 밑으로 m번 독립적으로 검정을 통과하면, 그 수가 합성수일 확률은 (1/4)m으로 급격히 줄어듭니다. 예를 들어 40번 통과하면 오류 확률이 약 10-24 수준으로 떨어지므로, 충분히 많은 라운드를 반복하면 사실상 결정적(deterministic) 판별에 가까운 신뢰성을 얻을 수 있습니다.

예제: 밑 2로 341이 합성수인지 검사하기

밀러-라빈 알고리즘을 밑(base) 2로 적용하여 341이 합성수인지 확인해 보겠습니다.

1단계: 341 − 1 = 340 = 22 × 85. 따라서 n = 341, k = 2, m = 85

2단계: 밑 a = 2 (주어진 값)

3단계: T = am mod n = 285 mod 341
210 = 1024 ≡ 1 (mod 341)이므로,
285 = (210)8 × 25 ≡ 1 × 32 = 32 (mod 341)
따라서 T = 32

4단계: T = 32는 1도 n − 1(= 340)도 아니므로 다음 단계로 진행합니다.

5단계: T = 322 mod 341 = 1024 mod 341 = 1
T가 제곱 과정에서 1이 되었지만, 그 직전 값이 −1(즉, n − 1)이 아니었습니다. 이는 1의 ‘자명하지 않은(nontrivial) 제곱근’이 존재한다는 뜻이며, 진짜 소수라면 발생할 수 없는 상황입니다.

결론: 341은 합성수입니다. 실제로 341 = 11 × 31로 분해됩니다. 참고로 341은 페르마 소수성 검정에서는 소수로 오인되는 대표적인 ‘페르마 유사소수(pseudoprime)’이지만, 밀러-라빈 검정은 이러한 속임을 정확히 걸러낼 수 있습니다.

장점

  • 매우 큰 수의 소수 여부도 효율적으로 검사할 수 있습니다.
  • 다른 소수성 검정에 비해 속도가 빠르기 때문에 여러 암호학 응용 분야에서 선호되는 검정 방법입니다.
  • 오일러(Euler) 검정이나 솔로베이-스트라센(Solovay-Strassen) 검정에 비해 더 강력하며, 오류 확률이 더 낮습니다.
  • 페르마 검정은 카마이클 수(Carmichael number) n에 대해 거짓말쟁이(liar)가 너무 많아 오류 확률이 1에 가까워지는 치명적인 단점이 있지만, 밀러-라빈은 이러한 문제를 효과적으로 방지합니다.