밀러-라빈 소수판정법

밀러-라빈 소수판정법(Miller-Rabin primality test)은 어떤 자연수의 유력 소수 여부를 알아내는 소수판정법으로, 페르마의 소정리나 솔로베이-슈트라센 소수판정법의 발전된 형태이다. 개리 밀러와 미하엘 라빈이 고안하였다.

판정 기준

임의의 홀수 자연수는 [math]\displaystyle{ N=d \cdot 2^k+1 }[/math]의 꼴로 표현할 수 있다. 여기서 [math]\displaystyle{ d }[/math]는 홀수이고, 자연수 [math]\displaystyle{ k }[/math]는 유일하게 결정된다. [math]\displaystyle{ N }[/math]이 소수이면 이와 서로소인 [math]\displaystyle{ a }[/math]에 대해 아래 두 식 중 하나가 성립한다.

• [math]\displaystyle{ a^d \equiv 1 \pmod N }[/math]
• [math]\displaystyle{ a^{d \cdot 2^r} \equiv -1 \pmod N \text{ for some } 0 \leq r\lt k }[/math]

이 조건을 통과하는 수를 강한 유력 소수(strong probable prime, SPRP)라 부른다. 만약 특정 지수 [math]\displaystyle{ b=d \cdot 2^r }[/math]에 대해 [math]\displaystyle{ a^2b \equiv 1, a^b \not\equiv \pm 1 \pmod N }[/math]이면 [math]\displaystyle{ N }[/math]은 소수가 아니다.

증명

증명은 페르마의 소정리에서 출발한다.

먼저 [math]\displaystyle{ N }[/math]이 소수이고 어떤 자연수 [math]\displaystyle{ x }[/math]가 주어져서 [math]\displaystyle{ x^2 \equiv 1 \pmod N }[/math]이면 [math]\displaystyle{ x \equiv \pm 1 \pmod N }[/math]이다. [math]\displaystyle{ N \mid x^2-1 }[/math]이면 [math]\displaystyle{ N \mid x+1 \text{ or } N \mid x-1 }[/math]이기 때문이다.

페르마의 소정리를 불러오면 [math]\displaystyle{ N-1=d \cdot 2^k, a^{d \cdot 2^k} \equiv 1 \pmod N }[/math]이다. 여기서 좌변의 제곱근을 구하면 [math]\displaystyle{ a^{d \cdot 2^{k-1}} \equiv \pm 1 \pmod N }[/math]이다. 우변이 -1이면 위 진술의 둘째 조건을 만족하므로 통과, +1이면 두 갈래로 나뉜다.

• [math]\displaystyle{ k=1 }[/math]이면 [math]\displaystyle{ a^d \equiv \pm 1 \pmod N }[/math]이므로 진술의 첫째 조건을 만족
• [math]\displaystyle{ k\gt 1 }[/math]이면 다시 한 번 제곱근을 취해서 [math]\displaystyle{ a^{d \cdot 2^{k-2}} \equiv \pm 1 \pmod N }[/math]를 이끌어낸다.

둘째 경우, 우변이 -1이면 둘째 조건을 만족하므로 통과, +1이면 똑같이 두 갈래로 나눈다.

이렇게 해서 [math]\displaystyle{ a }[/math]의 지수가 홀수가 될 때까지 제곱근 연산을 반복할 수 있고, 어떤 상황이라도 진술의 두 조건 중 하나를 만족한다는 사실을 알 수 있다.

검사 과정

• 검사할 자연수 [math]\displaystyle{ N }[/math]을 입력 받고 위 조건에 맞는 [math]\displaystyle{ d, k }[/math]를 찾는다. 그 다음 [math]\displaystyle{ N }[/math]보다 작은 임의의 자연수 [math]\displaystyle{ a }[/math]를 지정한다.
• [math]\displaystyle{ r=0 }[/math]으로 잡고, [math]\displaystyle{ a^d \equiv \pm 1 \pmod N }[/math]이면 "유력 소수"라 판정하고 알고리즘 종료한다.
• 바로 위 합동식이 안 맞으면 식을 제곱할 때마다 [math]\displaystyle{ r }[/math]의 값을 1 올리고, ±1과 합동인지 여부를 살핀다.
  • [math]\displaystyle{ r\lt k }[/math]일 때 -1과 합동인 시점이 나오면 "유력 소수"라 판정한다.
  • 어느 시점에서 -1을 거치지 않고 1과 합동인 값이 나오면 "합성수"라 판정한다.
  • [math]\displaystyle{ r=k-1 }[/math]이 될 때까지 제곱을 시도하고, -1과 합동인 시점이 안 나오면 "합성수"라 판정한다.

신뢰도

판정 기준을 통과한다고 해서 주어진 수가 소수라는 보장은 없다. 임의로 지정한 [math]\displaystyle{ a }[/math]에 대해 합동식 조건을 통과하는 수를 [math]\displaystyle{ a }[/math]를 밑으로 하는 강한 유사소수(strong pseudoprime to base [math]\displaystyle{ a }[/math])라 한다. 다만 서로 다른 [math]\displaystyle{ a }[/math]를 [math]\displaystyle{ k }[/math]개 골라서 일일이 검사할 때, 합성수가 이 모든 검사를 통과할 확률은 [math]\displaystyle{ 4^{-k} }[/math] 이하이다. 즉 검사를 여러 번 시행한다면 강한 유사소수를 효과적으로 걸러낼 수 있다. 참고로 솔로베이-슈트라센 소수판정법 기준 확률은 [math]\displaystyle{ 2^{-k} }[/math] 이하이다.

[math]\displaystyle{ a }[/math]를 여러 개 고른다고 할 때, 이들 수는 가급적 서로소가 되는 것이 좋다. 이 때문에 보통 밀러-라빈 판정법을 시행할 때는 대개 작은 소수들을 밑으로 삼는다. 주어진 수가 아주 큰 수가 아닌 경우, 소수를 몇 개 골라서 시행해도 [math]\displaystyle{ N }[/math]이 확실한 소수라는 사실을 알 수 있다.

[math]\displaystyle{ \psi_k }[/math]는 가장 작은 소수 [math]\displaystyle{ k }[/math]개를 골랐을 때, 이들 소수를 밑으로 하는 검사를 모두 통과하는 가장 작은 유사소수라 하자. 그러면 현재까지 작은 유사소수에 대해 조사를 한 결과 아래 값들을 찾았다.

• [math]\displaystyle{ \psi_1 =2047 =23 \cdot 89 }[/math]
• [math]\displaystyle{ \psi_2 =1373653 =829 \cdot 1657 }[/math]
• [math]\displaystyle{ \psi_3 =25326001 =2251 \cdot 11251 }[/math]
• [math]\displaystyle{ \psi_4 =3215031751 =151 \cdot 751 \cdot 28351 }[/math]
• [math]\displaystyle{ \psi_5 =2152302898747 = 6763 \cdot 10627 \cdot 29947 }[/math]
• [math]\displaystyle{ \psi_6 =3474749660383 =1303 \cdot 16927 \cdot 157543 }[/math]
• [math]\displaystyle{ \psi_7=\psi_8 =341550071728321 =10670053 \cdot 32010157 }[/math]

이를테면 [math]\displaystyle{ \psi_4 }[/math]의 경우 가장 작은 소수 4개, 즉 2, 3, 5, 7을 [math]\displaystyle{ a }[/math]로 고를 때 위 판정 기준을 모두 통과하는 유사소수 중 가장 작은 값이다. 달리 말해 [math]\displaystyle{ \psi_4 }[/math]보다 작은 자연수를 시험하고 싶다면 이들 4개 소수로 테스트를 돌려서 소수 여부를 확실히 밝혀낼 수 있는 것이다.

물론 무조건 '가장 작은 소수'를 밑으로 고를 필요는 없다. 밑으로 고를 수를 적절히 조합하면 특정 범위의 자연수에서 소수 여부를 밝히는데 필요한 테스트 횟수를 줄일 수 있다. 관련 정보는 여기를 참고.

소인수분해

만약 위와 같이 테스트를 돌릴 때, 제곱을 반복하는 도중 [math]\displaystyle{ x \not \equiv \pm 1, x^2 \equiv 1 \pmod N }[/math] 관계식을 발견하면 [math]\displaystyle{ N }[/math]이 합성수라는 사실을 도출함과 더불어 소인수분해를 할 수 있다. [math]\displaystyle{ N \mid x^2-1, N \nmid x \pm 1 }[/math]이면 [math]\displaystyle{ \gcd(x \pm 1, N) }[/math]의 값은 1과 [math]\displaystyle{ N }[/math] 사이의 값을 가지고, 이에 따라 주어진 수의 비자명한 약수를 찾을 수 있다.