밀러-라빈 소수 판별법
밀러-라빈 소수 판별법 (Miller-Rabin Primality Test) 은 어떤 정수 $N$이 소수인지 아닌지 빠르게 판단하는 방법입니다.
가장 기초적인 소수 를 판별하는 방법은 $2$부터 $\sqrt{N}$까지 나누어보는 방법 을 쓰곤 했습니다.
더더욱 빠르고, 그러면서도 정확한 소수 판별법을 위해서 아주 중요한 정수론의 정리 한가지를 이용해줍니다.
페르마의 소정리
1. 모든 소수 $p$와 모든 자연수 $a$에 대하여 $a^{p} \equiv a \pmod{p}$ 이다.
2. 소수 $p$와 $a$가 서로소 이면 $a^{p - 1} \equiv 1 \pmod{p}$ 이다.
페르마의 소정리는 아주 간결하고 꽤나 강력하지만, 완전하진 못합니다.
모든 소수 $p$가 이를 만족하지만, 가끔씩 어떤 자연수 $a$에 대하여 $a^{N-1} \equiv 1 \pmod{N}$인 합성수 $N$이 존재하기도 합니다.
예를 들어, $341$같은 Poulet Number 는 $2^{340} \equiv 1 \pmod{341}$이지만 $341 = 11 \times 31$입니다.
게다가 모든 자연수 $a$에 대하여 $a^{N} \equiv a \pmod{N}$가 되는 합성수 $N$ ( 카마이클 수 )도 있으므로 페르마의 소정리 만으로는 부족합니다.
보조정리
소수 $p$에 대하여 $x^{2} \equiv 1 \pmod{p}$이면 $x \equiv 1 \pmod{p}$이거나 $x \equiv -1 \pmod{p}$이다.
보조정리 증명
증명은 유클리드의 보조정리 에 의해 쉽게 할 수 있습니다.
유클리드의 보조정리
소수 $p$에 대하여 $ab \equiv 0 \pmod{p}$이면 $a \equiv 0 \pmod{p}$이거나 $b \equiv 0 \pmod{p}$이다.
$x^{2} \equiv 1 \pmod{p}$에서 $x^{2} - 1 \equiv 0 \pmod{p}$이고, $(x - 1)(x + 1) \equiv 0 \pmod{p}$이므로
$x \equiv 1 \pmod{p}$이거나 $x \equiv -1 \pmod{p}$임을 쉽게 알 수 있습니다.
페르마의 소정리와 보조정리를 사용해주기 위해서 $N - 1$을 $N - 1 = 2^{s} \times d$로 쪼개줍니다.
이때, $s$는 자연수, $d$는 홀수입니다.
즉, $d$는 $N - 1$을 $2$로 나눌 수 있을 때까지 계속 나누고 남은 수, $s$는 $N - 1$을 $2$로 나눈 횟수입니다.
$N$이 짝수이면 $s = 0$이 되는데, 애초에 짝수인 소수는 $2$밖에 없으므로, $N$은 홀수라고 생각해줍니다. 그래야 $s \geq 1$이 됩니다.
$2 \leq a \leq N - 1$인 적당한 정수 $a$를 선택해 줍니다. (어떤 $a$값을 선택할 지는 후술)
$a^{d} \pmod{N}$의 값을 구해줍니다. 이후 $a^{d} \pmod{N}$의 값에 따른 두가지 경우로 나뉩니다.
1. $a^{d} \equiv -1 \pmod{N}$ 이거나 $a^{d} \equiv 1 \pmod{N}$인 경우
이 경우엔 $a^{N-1} \equiv a^{d \times 2^{s}} \equiv { \left(a^{d} \right)}^{2^{s}} \equiv {(-1)}^{2^{s}} \equiv 1 \pmod{N}$ 이거나, ($-1$의 짝수 거듭 제곱은 $1$)
${ \left(a^{d} \right)}^{2^{s}} \equiv {(1)}^{2^{s}} \equiv 1 \pmod{N}$ 이므로 페르마의 소정리를 통과합니다. 따라서 "아마도 소수" 라고 볼 수 있습니다.
2. $a^{d} \not\equiv \pm 1 \pmod{N}$ 인 경우
이 경우에는 또 3가지 경우로 나누어집니다. $a^{d} \equiv b \pmod{N}$ 라고 한다면
2 - 1. $b^{2} \equiv -1 \pmod{N}$ 일 경우
$a^{d \times 2} \equiv b^{2} \pmod{N}$에서 $a^{N-1} \equiv a^{d \times 2^{s}} \equiv { \left(a^{d \times 2} \right)}^{2^{s - 1}} \equiv {(-1)}^{2^{s - 1}} \equiv 1 \pmod{N}$ 이므로,
페르마의 소정리를 통과합니다. 따라서 "아마도 소수" 라고 볼 수 있습니다.
2 - 2. $b^{2} \equiv 1 \pmod{N}$ 일 경우
위의 보조정리에 의해, $N$이 소수일 때는 $b^{2} \equiv 1 \pmod{N}$이면 $b \equiv 1 \pmod{N}$이거나 $b \equiv -1 \pmod{N}$여야 하지만, 2번의 전제가 $a^{d} \equiv b \not\equiv \pm 1 \pmod{N}$인 경우였으므로,
이 경우는 $N$이 확실히 합성수라는 것을 말해줍니다. "아마도 소수"같은 것이 아닌 확실히 합성수 입니다.
2 - 3. $b^{2} \not\equiv \pm 1 \pmod{N}$ 일 경우
이 경우에도 3가지로 나누어서, $b^{2} = c$라 하고 $c^{2} \pmod{N}$ 의 값을 구해서 2번으로 돌아가 2 - 1, 2 - 2, 2 - 3 의 단계를 반복합니다.
만약에 이렇게 계속 $b^{2}, b^{4}, b^{8} \cdots$로 올라가면서도 끝끝내 $a^{d \times 2^{s-1}} \not\equiv \pm1 \pmod{N}$이라는 결과까지 가면, $N$은 확실히 합성수입니다.
또한, $a^{d \times 2^{s-1}} \pmod{N}$의 값까지 계산했는데 소수인지 아닌지 판정이 안났다면, 굳이 $a^{d \times 2^{s}} \pmod{N}$의 값을 계산하지 않고 합성수로 판단해도 좋습니다.
$a^{d \times 2^{s}} \equiv -1 \pmod{N}$이면 페르마의 소정리에 의해서 $N$이 소수가 아니고,
$a^{d \times 2^{s}} \equiv 1 \pmod{N}$이면 페르마의 소정리에 의해서는 소수일 수 있지만, 2-2에서 설명한 논리대로 확실히 합성수이고,
그 외의 경우에는 페르마의 소정리에 의해서 당연하게 소수가 아니게 됩니다.
$a$를 선택하는 법
$a$값은 어떻게 선택해야할까요?
밀러가 처음 발표한 소수판별법은, 일반화 리만 가설 이 맞다는 가정하에 $2 \leq a \leq 2 {\left(\ln{N}\right)}^{2}$인 모든 정수 $a$에 대해서만 검사하면 된다고 했습니다. ($\ln{n}$은 자연로그함수 입니다.)
라빈은 리만가설을 제외하고, 적당히 $2 \leq a \leq N - 1$인 $a$를 랜덤으로 128개 정도 뽑아서 판별하면 대충 소수가 아니겠냐는 확률적 알고리즘으로 바꿉니다.
(어떤 $a$이든 위 판별법이 틀릴 확률이 아무리 높아도 $\frac{1}{4}$보다는 낮다는게 알려져있고, 128번 반복하면 $\frac{1}{4^{128}} = \frac{1}{2^{256}}$이라는 확률이 나와 거의 일어나지 않을 일이기 때문)
그러나 $N$이 아주 크지 않다면, $a$의 갯수를 획기적으로 줄일 수 있다는게 노가다로 알려져 있습니다.
더 빠른 소수 판별법을 위해 직접 노가다로 고생하신 4분 Pomerance, Selfridge, Wagstaff, Jaeschke 님에게 경의를 표하면서 결과를 감상하도록 해봅니다.
$N < 2,047$이면, $a = 2$일 때만 검사해도 충분합니다.
$N < 1,373,653$이면, $a = 2$, $3$일 때 두 번만 검사해도 충분합니다.
$N < 25,326,001$이면, $a = 2$, $3$, $5$일 때 세 번만 검사해도 충분합니다.
$N < 3,215,031,751$이면, $a = 2$, $3$, $5$, $7$일 때만 검사해도 충분합니다.
($2^{31} < 3,215,031,751$이므로, int형 범위에서는 $a = 2$, $3$, $5$, $7$일 때만 검사해도 충분합니다.)
$N < 2,152,302,898,747$이면, $a = 2$, $3$, $5$, $7$, $11$일 때만 검사해도 충분합니다.
$N < 3,474,749,660,383$이면, $a = 2$, $3$, $5$, $7$, $11$, $13$일 때만 검사해도 충분합니다.
$N < 341,550,071,728,321$이면, $a = 2$, $3$, $5$, $7$, $11$, $13$, $17$일 때만 검사해도 충분합니다.
Feitsma, Galway, Jiang, Deng 이 4분이 결과를 더더욱 확장시켜주었습니다.
$N < 3,825,123,056,546,413,051$이면, $a = 2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$일 때만 검사해도 충분합니다.
$N < 18,446,744,073,709,551,616 = 2^{64}$이면, $a = 2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$일 때만 검사해도 충분합니다.
(즉, unsigned long long 범위에서도 12번만 검사해도 충분합니다.)
Sorenson, Webster 두 분은 더 큰 정수 범위에서 검사하셨습니다.
$N < 318,665,857,834,031,151,167,461$이면, $a = 2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$일 때만 검사해도 충분합니다.
$N < 3,317,044,064,679,887,385,961,981$이면, $a = 2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$일 때만 검사해도 충분합니다.
간단하게 밀러-라빈 소수판별법을 다시 정리 해보겠습니다.
0. 소수인지 합성수인지 판별할 $3$이상의 홀수 $N$을 입력받습니다.
Q . $3$이상의 홀수 이외의 수는 어떻게 판단하나요?
A . $1$은 소수가 아닌걸로, $2$는 소수인걸로, $2$ 이외의 2의 배수는 합성수로 편의상 미리 판단해줍니다.
1. $N - 1 = d \times 2^{s}$인 홀수 $d$와 자연수 $s$를 구해줍니다.
$N - 1$을 홀수가 될 때까지 계속 $2$로 나누면 $d$가 나오고, $2$로 나눈 횟수가 $s$가 됩니다.
2. 적당한 자연수 $a$를 가져옵니다.
$N$이 위에서 설명드린 ("$a$를 선택하는 법") 범위 안에 있다면 그 $a$의 집합에서만 가져오면 됩니다.
$N$이 위에서 설명드린 범위 안에 없다면 $2$부터 $2 {\left( \ln{N} \right)}^{2}$까지의 모든 정수 $a$로 판별해야 합니다.
$2$부터 $2 {\left( \ln{N} \right)}^{2}$를 전부 계산하기 귀찮다면, $2$이상 $N - 1$ 이하인 $a$를 랜덤하게 $128$개 가량 골라 판별해도 됩니다. (완벽한 정답은 보장 불가)
Q. 꼭 $N$과 서로소인 $a$를 가져와야 되나요?
A. $2 \leq a \leq N - 1$ 인데 $a$와 $N$이 서로소가 아니면 어차피 $a^{N - 1} \equiv 1 \pmod{N}$이 나오지 않을테니 그 부분은 크게 신경 쓰지 않으셔도 됩니다.
3. a, s, d, N을 매개변수로 받는 함수(MRTest)를 정의해서 $a^{d} \equiv b_{0} \pmod{N}$인 $b_{0}$을 구해줍니다.
$b_{0} \equiv \pm 1 \pmod{N}$이면 아마도 소수라고 판단합니다. (return True)
4. $b_{n} \equiv {\left(b_{n - 1}\right)}^{2} \pmod{N}$ 으로 정의된 수열에 대해 다음을 판단합니다.
$0 \leq r \leq s - 1$인 어떤 자연수 $r$에 대하여 $b_{r} \equiv -1 \pmod{N}$ 이면 $N$을 아마도 소수라고 판단합니다.
그 외의 경우는 전부 확실한 합성수로 판단합니다. (return False)
5. 2번, 3번, 4번 과정을 계속 반복합니다.
한번이라도 MRTest 함수에서 False가 나왔다면 즉시 합성수로, 더이상 검사할 $a$가 없으면 확실한 소수로 출력합니다.
0번부터 5번까지의 과정을 반복한 코드는 다음과 같습니다. (Python)
Q. 리만가설이 맞았다는 거에 의존해서 $2 {\left(\ln{N}\right)}^{2}$까지 검사하는데, 리만가설은 아직 안풀렸으니 불확실한거 아닌가요? 써도 되는건가요?
A. $2 {\left(\ln{N}\right)}^2$까지 검사하여 소수라고 출력했는데 사실 합성수였다면 리만가설은 틀렸다라는게 됩니다.
따라서 밀러라빈 소수판별법을 사용하고 틀린 결과가 나왔다면 단점은 다음과 같습니다.
단점 :
소수 판별 한 번 틀림
장점은 다음과 같습니다.
장점 :
200년 난제인 리만가설 해결 (그것도 "리만가설이 틀렸다"로)
밀레니엄 문제 해결로 클레이 연구소에서 100만달러 (약 12억원) 수령
40세 이하라면 필즈상 수상
필즈상 이외 각종 수학 관련 상(+상금) 수상
그 외에도 자잘한 것들로는 전세계 모든 정수론 교재에 이름 등재, 리만가설 해결 공로로 대통령 표창장 수령 등등...
그러면 안되는거지만 가끔 쓰면서도 이 알고리즘이 틀렸으면...이라는 생각을 가끔씩 하게 됩니다.
Q. 파이썬이 아닌 다른 언어에서 큰 정수의 구현을 완료한 상태(혹은 JS의 BigInt 처럼 정수끼리의 연산만 가능한 상태)인데,
정수만 가지고 자연로그함수 $\ln{N}$의 값을 어떻게 구하고, $2 {\left(\ln{N}\right)}^2$의 값을 어떻게 구하죠?
A. $2^{k + 1} > N \geq 2^{k}$인 $k$ 값을 구합니다.
각 변에 자연로그를 씌워주면 $(k + 1)\ln{2}> \ln{N} \geq k \ln{2}$ 입니다. (모든 항이 $1$ 이상이므로 가능합니다.)
왼쪽의 양 변을 제곱해주면 $(k + 1)^{2} {\left( \ln{2} \right)}^{2} > {\left( \ln{N} \right)}^{2}$이 됩니다.
이 때, $\frac{123}{256} - {\left(\ln{2}\right)}^2 = 0.00001573...$ 정도이므로
$(k + 1)^{2} \frac{123}{256} > {\left( \ln{N} \right)}^{2}$입니다.
양 변에 $2$를 곱해줘서 $(k + 1)^{2} \frac{123}{128} > 2 {\left( \ln{N} \right)}^{2}$가 되므로,
$(k + 1)^{2}$의 값에, $123$을 곱하고 다시 $128$로 나눈 몫에다가 $1$을 더해주면 넉넉하게 $2 {\left( \ln{N} \right)}^{2}$과 비슷하면서도 조금 더 큰 값을 얻을 수 있습니다.
귀찮으시면 그냥 $2$부터 $(k + 1)^{2}$까지 탐색하시면 됩니다.
Q. 더 최적화 시킬 순 없나요?
A. 저기에서 약간 더 다른 개념들을 섞어서 제 개인적으로 PS에 사용중인 소수판별법 코드는 따로 있습니다.
혹은 밀러-라빈 소수 판별법이 필요한 상태가 아닌, 에라토스테네스의 체 등을 사용해야 하는 경우일 수 있습니다.
큰 범위의 (1부터 1천만까지 같은) 소수들을 얻으려면 에라토스테네스의 체를 사용해야 합니다.
Q. 밀러-라빈 소수 판별법보다 더 빠르게 소수를 판별할 수는 없나요?
A. 뤼카 수열 소수판별법 같은 확률적인 소수판별법을 섞어서 베일리-PSW 소수판별법을 만들어 쓰실 수 있습니다. 대신 이 경우에는 "소수"라고 결과가 나왔는데 합성수일 가능성이 있습니다.