밀러-라빈 소수판별법은 정수의 소수 여부를 판단하기 위해 사용되는 확률적 소수 판별 알고리즘이다. 이 방법은 1976년 마이클 밀러와 1980년 론 라빈이 각각 제안한 소수 판정 기법을 결합한 것으로, 주어진 정수 $n > 2$에 대해 무작위로 선택한 기반(base) $a$에 대해 일련의 거듭 제곱과 나머지 연산을 수행한다.
기본 원리
- $n-1$을 $2^s \cdot d$ (단, $d$는 홀수) 형태로 표현한다.
- 무작위 기반 $a$ ( $2 \le a \le n-2$ )를 선택한다.
- $x = a^{d} \mod n$ 을 계산한다.
- $x = 1$ 혹은 $x = n-1$ 이면 해당 기반에 대해 $n$은 “가능성 소수”(probable prime)이다.
- 위 조건을 만족하지 않으면, $x$를 $s-1$번 반복하여 $x = x^2 \mod n$을 계산한다.
- 반복 과정 중에 $x = n-1$ 이 나타나면 해당 기반에 대해 $n$은 “가능성 소수”이다.
- 반복이 모두 끝날 때까지 $x = n-1$ 이 나타나지 않으면 $n$은 합성수이다.
특성
- 확률적 성격: 선택한 기반의 수와 무작위성에 따라 오류 확률이 존재한다. 일반적으로 $k$개의 서로 다른 기반을 사용하면 오류 확률은 $4^{-k}$ 이하로 감소한다.
- 시간 복잡도: 각 기반에 대해 $\mathcal{O}(\log^3 n)$ 연산이 필요하며, 전체 복잡도는 선택한 기반 수에 비례한다.
- 결정적 변형: 특정 범위(예: 32비트 정수)에서는 미리 정해진 제한된 기반 집합을 사용함으로써 오류 없이 소수를 판정할 수 있다. 이러한 변형은 “결정적 Miller–Rabin 테스트”라 불린다.
실제 활용
- 암호학에서 키 생성 과정(특히 RSA)의 소수 선택 단계에 널리 적용된다.
- 대규모 정수의 소수성 검증이 필요한 수론 연구 및 컴퓨터 과학 분야에서도 기본 도구로 활용된다.
- 파이썬, C++, 자바 등 주요 프로그래밍 언어의 표준 라이브러리나 수학 패키지에서 구현되어 제공된다.
제한점
- 확률적 테스트이므로 오류(소수를 합성수로 오판하거나 그 반대) 가능성이 존재한다. 오류를 완전히 배제하려면 추가적인 결정적 소수 판별법(예: AKS 시험)과 결합하거나 충분히 많은 기반을 사용해야 한다.
참고
- Miller, G. L. (1976). “Riemann’s hypothesis and tests for primality”. Journal of Computer and System Sciences.
- Rabin, M. O. (1980). “Probabilistic algorithm for testing primality”. Journal of Number Theory.
위와 같이 밀러-라빈 소수판별법은 현대 수학 및 정보보안 분야에서 핵심적인 확률적 소수 판정 기술로 인정받고 있다.
