암호 기술에서는 수백 자리의 큰 수가 소수인지 빠르게 확인해야 할 때가 있습니다. 2부터 √n까지 모두 나누어 보는 방법은 n이 커지면 현실적으로 사용할 수 없습니다. 밀러-라빈(Miller–Rabin) 검사는 모듈러 거듭제곱으로 합성수의 증거를 찾는 확률적 소수 판정법입니다. 검사가 ‘합성수’라고 하면 그 결론은 확정적입니다. 여러 밑을 검사해 모두 통과하면 ‘확률적 소수(probable prime)’로 판정하며, 무작위 밑을 독립적으로 k번 고른 표준 분석에서는 특정 합성수가 모두 통과할 확률의 상한이 4^−k입니다. 이 수치는 무작위 선택과 구현 조건을 전제로 한 최악 상한이지 입력 자체가 소수일 사후확률을 그대로 뜻하지는 않습니다.
출발점은 페르마의 소정리
소수 p와 p의 배수가 아닌 정수 a에 대해 페르마의 소정리는 a^(p−1)≡1 (mod p)이라고 말합니다. 따라서 어떤 n과 a에서 a^(n−1) mod n이 1이 아니면 n은 확실한 합성수입니다. 그러나 역은 성립하지 않습니다. 합성수인데도 특정 밑 a에서 이 합동식을 만족하는 페르마 의사소수가 있고, 모든 서로소인 밑에 대해 통과하는 카마이클 수도 있습니다. 단순 페르마 검사는 이런 합성수에 속을 수 있습니다. 밀러-라빈 검사는 n−1에서 2의 거듭제곱을 분리하고 중간 제곱 결과까지 확인해 더 강한 조건을 적용합니다.
n−1을 2^s×d로 분해한다
검사 대상 n이 2보다 큰 홀수라면 n−1은 짝수입니다. n−1을 2로 계속 나누어 n−1=2^s·d, d는 홀수인 형태로 씁니다. 밑 a를 2≤a≤n−2 범위에서 고르고 x=a^d mod n을 계산합니다. x가 1 또는 n−1이면 이 밑에 대한 검사를 통과합니다. 그렇지 않으면 x를 제곱해 x←x² mod n으로 바꾸는 일을 최대 s−1번 반복합니다. 도중에 n−1이 나오면 통과하고, 끝까지 나오지 않으면 a는 n이 합성수임을 증명하는 증인(witness)입니다.
왜 1과 −1을 확인하는가
소수 p에 대한 나머지 체계에서는 x²≡1 (mod p)의 해가 x≡1 또는 x≡−1뿐입니다. n−1은 모듈러 n에서 −1과 같습니다. a^d를 반복해서 제곱하면 마지막에는 a^(n−1)에 도달합니다. 소수라면 최종값이 1이 되기 전에 처음 만나는 1의 제곱근은 1 또는 −1이어야 합니다. 시작값이 1이거나, 제곱 과정 중 −1이 나타나는지를 검사하는 까닭입니다. 1도 −1도 아닌 값이 제곱되어 1이 되는 비자명한 제곱근을 발견하면 n은 소수가 될 수 없습니다. 합성수의 모듈러 구조에서는 이런 값이 존재할 수 있습니다.
221을 밑 2로 검사하는 예
n=221을 검사하겠습니다. 220=2²×55이므로 s=2, d=55입니다. 밑 a=2를 택해 빠른 모듈러 거듭제곱으로 x=2^55 mod 221을 계산하면 128입니다. 128은 1도 220도 아닙니다. s−1=1번 제곱하면 128² mod 221=30이 됩니다. 이 값도 220이 아니므로 2는 합성수 증인이고 221은 합성수입니다. 실제로 221=13×17입니다. 알고리즘은 인수 13과 17을 직접 찾아야 결론을 내리는 것이 아니라, 소수라면 반드시 만족해야 하는 제곱 사슬의 성질이 깨졌음을 확인합니다.
한 번 통과했다고 소수는 아니다
합성수 n도 일부 밑에서는 밀러-라빈 조건을 통과할 수 있습니다. 이런 밑을 강한 거짓말쟁이(strong liar)라고 하고, n을 그 밑에 대한 강한 의사소수라고 합니다. 그래서 한 밑을 통과한 결과는 소수의 증명이 아닙니다. 중요한 정리는 홀수 합성수에 대해 가능한 밑 가운데 강한 거짓말쟁이의 비율이 최대 1/4이라는 것입니다. 무작위 밑을 독립적으로 k번 선택하면 특정 합성수가 모든 검사를 통과할 확률은 최대 (1/4)^k입니다. 10번이면 1/1,048,576 이하, 20번이면 1/1,099,511,627,776 이하라는 최악 상한이 됩니다.
이 확률을 ‘검사를 20번 통과한 수가 합성수일 확률’이라고 곧바로 읽으면 베이즈 정리에 필요한 사전분포를 빠뜨립니다. 정리의 내용은 입력이 합성수라고 고정했을 때 독립적이고 균등한 무작위 밑 선택이 모두 나쁜 밑에 걸릴 조건부 확률의 상한입니다. 실제 후보가 어떤 방식으로 만들어졌는지, 작은 소수 나눗셈을 먼저 했는지, 난수 생성기가 올바른지도 최종 신뢰도에 영향을 줍니다. 확률적 알고리즘의 오차 상한과 현실 시스템 전체의 고장 확률을 구분해야 합니다.
빠른 모듈러 거듭제곱으로 큰 지수를 처리한다
a^d를 그대로 d−1번 곱하면 지수가 큰 경우 느리고 중간 정수도 거대해집니다. 제곱-곱(square-and-multiply) 방식은 d의 이진 표현을 따라 제곱과 필요한 곱셈을 하고 매번 n으로 나머지를 취합니다. 필요한 곱셈 횟수는 지수 d 자체가 아니라 비트 길이 log d에 비례합니다. 예를 들어 지수를 절반씩 줄이면서 짝수면 밑을 제곱하고, 홀수면 결과에 밑을 한 번 곱한 뒤 진행할 수 있습니다. 큰 정수 곱셈의 비용까지 포함한 정확한 복잡도는 사용한 산술 알고리즘에 따라 달라지지만, 시행 나눗셈보다 매우 큰 후보를 효율적으로 검사할 수 있는 핵심이 이 이진 모듈러 지수 계산입니다.
검사 전 처리하면 좋은 값
n<2는 소수가 아니고 2와 3은 소수입니다. 2보다 큰 짝수는 즉시 합성수로 판정할 수 있습니다. 작은 소수들로 먼저 나누어 떨어지는지 확인하면 명백한 합성수를 저렴하게 걸러낼 수 있습니다. 밑 a와 n의 최대공약수가 1보다 크면 그 자체로 합성수의 증거가 됩니다. 입력 범위, 음수 처리, 0과 1의 처리도 명시해야 합니다. 모듈러 곱셈에서 고정 폭 정수의 곱이 넘칠 수 있으므로 더 넓은 자료형, 몽고메리 곱셈 또는 안전한 큰 정수 라이브러리를 사용해야 합니다.
고정 밑을 쓰는 결정적 검사는 범위가 필요하다
컴퓨터의 32비트나 64비트 정수처럼 n의 상한이 정해져 있으면 연구로 확인된 특정 밑 집합을 검사해 해당 범위에서 결정적으로 판정할 수 있습니다. 이 경우 무작위 선택이 아니며 그 범위 안의 모든 합성수에 적어도 하나의 증인이 포함된다는 결과를 사용합니다. 하지만 어떤 고정 밑 목록이든 모든 크기의 정수에 그대로 통한다는 뜻은 아닙니다. 목록마다 보장되는 상한이 다르고, 범위를 넘으면 그 밑들을 모두 통과하는 합성수가 존재할 수 있습니다. 구현 문서에는 밑 목록뿐 아니라 검증된 입력 범위를 반드시 함께 기록해야 합니다.
소수 판정과 소수 증명은 다르다
무작위 밀러-라빈 검사를 여러 번 통과한 수는 매우 높은 신뢰도의 확률적 소수지만, 통과 기록만으로 일반적인 의미의 결정적 소수 증명서가 생기는 것은 아닙니다. 반드시 증명 가능한 소수가 필요하면 ECPP 같은 소수 증명 알고리즘이나 조건에 맞는 결정적 방법을 사용할 수 있습니다. 반대로 RSA 키 생성과 같은 응용에서는 표준이 정한 후보 생성 절차, 시행 나눗셈과 반복 확률 검사를 조합하기도 합니다. 보안 구현에서는 임의로 반복 횟수와 밑을 정하지 말고 적용되는 표준과 검증된 암호 라이브러리를 따라야 합니다.
밀러와 라빈의 역할
게리 밀러는 1976년에 확장 리만 가설을 전제로 한 결정적 다항 시간 소수 판정 결과를 발표했습니다. 마이클 라빈은 1980년에 관련 검사를 무작위화해 오류 확률을 명시적으로 제한하는 실용적 알고리즘을 제시했습니다. 오늘날 밀러-라빈이라는 이름은 보통 n−1=2^s·d 분해와 무작위 밑 반복을 사용하는 강한 확률적 검사를 가리킵니다. 역사적 원형의 조건부 결정적 검사와 현대 구현의 무작위 검사를 구별하면 ‘확률적 알고리즘인데 왜 밀러의 이름이 붙었는가’라는 혼동을 줄일 수 있습니다.
알고리즘을 단계별로 정리
- n<2, 작은 소수, 짝수 같은 예외를 먼저 처리합니다.
- 홀수 n에 대해 n−1=2^s·d가 되도록 2를 모두 분리합니다.
- 범위 안에서 밑 a를 고르고 필요하면 gcd(a,n)을 확인합니다.
- x=a^d mod n을 빠른 모듈러 거듭제곱으로 계산합니다.
- x가 1 또는 n−1이면 이 라운드를 통과시킵니다.
- 최대 s−1번 x←x² mod n을 계산해 n−1이 나오면 통과시킵니다.
- 끝까지 n−1이 나오지 않으면 합성수로 확정합니다.
- 통과했다면 독립적인 새 밑으로 필요한 횟수만큼 반복합니다.
자주 생기는 오해
- 밀러-라빈이 합성수라고 판정하면 오판 가능성은 없습니다. 확률 오류는 합성수를 확률적 소수로 통과시키는 방향에만 있습니다.
- 한 라운드의 최악 통과 확률 상한은 1/4이며 k번의 독립 무작위 검사에서는 4^−k입니다.
- 같은 밑을 반복하거나 편향된 난수를 사용하면 독립 반복 상한을 그대로 적용할 수 없습니다.
- 고정된 몇 개의 밑으로 결정적 판정을 할 때는 반드시 그 밑 집합이 보장하는 입력 상한이 필요합니다.
- 페르마 검사와 밀러-라빈 검사는 같지 않습니다. 후자는 반복 제곱의 중간값까지 검사합니다.
- 확률적 소수 판정과 검증 가능한 소수 증명은 목적과 보장이 다릅니다.
밀러-라빈 검사는 큰 수를 직접 인수분해하지 않고도 소수가 가져야 할 모듈러 제곱 사슬을 확인합니다. n−1에서 2의 거듭제곱을 분리하고 a^d부터 반복 제곱해 1과 −1의 출현을 검사하면 많은 합성수를 빠르게 찾아냅니다. 무작위 밑을 독립적으로 반복할수록 최악 오류 상한은 4^−k로 줄어듭니다. 다만 결정적 고정 밑 검사는 검증된 수 범위 안에서만 사용하고, 보안 목적이라면 표준 절차와 검증된 구현을 적용해야 합니다.
반복 횟수만큼 중요한 밑 선택
확률 상한 4^−k는 각 라운드의 밑이 허용 범위에서 균등하고 독립적으로 선택된다는 전제에서 나옵니다. 난수 생성기의 내부 상태가 예측되거나 같은 밑이 반복되면 라운드 수만 늘어날 뿐 새로운 증인을 찾을 가능성이 기대만큼 커지지 않습니다. 반대로 입력 상한이 고정된 정수 라이브러리는 검증된 결정적 밑 목록을 사용해 난수 의존성을 없앨 수 있습니다. 두 방식은 섞어 설명하면 안 됩니다. 임의 정밀도 정수에는 충분한 독립 무작위 라운드를 적용하고, 고정 폭 정수에는 해당 범위가 증명된 밑 집합을 적용하는 식으로 보장 근거를 분명히 해야 합니다.
암호용 소수 후보를 만들 때는 밀러-라빈 통과만 확인하지 않고 후보의 비트 길이와 홀수 여부, 작은 소수 인수, 적용 표준이 요구하는 추가 조건을 함께 검사합니다. RSA에서는 두 소수의 선택과 차이, 공개 지수와의 관계 등 키 생성 전체 절차가 안전성에 영향을 줍니다. 소수 판정 알고리즘 한 부분이 정확해도 약한 난수로 후보를 만들거나 비밀값이 노출되면 안전한 키가 되지 않습니다. 따라서 직접 작성한 예제 코드는 학습용으로 두고 실제 보안 기능은 표준에 맞게 검증된 라이브러리를 사용하는 것이 필요합니다.
참고 자료
- Gary L. Miller, Riemann's Hypothesis and Tests for Primality (1976): https://doi.org/10.1016/S0022-0000(76)80043-8
- Michael O. Rabin, Probabilistic Algorithm for Testing Primality (1980): https://doi.org/10.1016/0022-314X(80)90084-0
- NIST FIPS 186-5, Digital Signature Standard—prime generation and primality testing: https://doi.org/10.6028/NIST.FIPS.186-5