밀러-라빈 판정법
정리 1
홀수 $n,q$ 를 $n-1 = 2^{k} q$ 와 같이 나타내자. $$ a \nmid n \\ a^{q} \not\equiv 1 \pmod{n} $$ 이면서 모든 $i = 0, 1, \cdots , (k-1)$ 에 대해 $$ a^{2^{i} q} \not\equiv -1 \pmod{n} $$ 를 만족하는 $ a$ 가 존재하면 $n$ 은 합성수다.
설명
계산량이 늘어난만큼 페르마 판정법을 통과하는 합성수도 걸러낼 가능성이 있다.
예로써 카마이클 수인 $561$ 은 $n-1 = 560 = 2^4 \cdot 35$ 이 $2^{35} \equiv 263 \pmod{561}$ 이므로 $561$ 이 소수가 아님을 빠르게 확인할 수 있다. 이때 판정에 쓰인 $a=2$ 와 같은 수를 밀러-라빈 증거miller-Rabin Witness라 한다. 물론 모든 $a$ 에 대해서 판정법을 통과하더라도 $n$ 이 소수라는 말은 아니다.
증명
홀수 소수 $p$ 를 $p-1 = 2^{k} q$ 와 같이 두자.페르마의 소정리에 의해 $$ a^{p-1} \equiv a^{2^{k} q} \equiv 1 \pmod{p} $$
만약 $a^{2^{k-1} q} \equiv -1 \pmod{p}$ 이 아니라면 $a^{2^{k-2} q} \equiv -1 \pmod{p}$ 일 수 있다.
만약 $a^{2^{k-2} q} \equiv -1 \pmod{p}$ 도 아니라면 $a^{2^{k-3} q} \equiv -1 \pmod{p}$ 일 수 있다.
마찬가지로 $a^{q} , a^{2q} , \cdots , a^{2^{k-2} q} , a^{2^{k-1} q}$ 중 적어도 하나는 $\pmod{p}$ 에서 $(-1)$ 과 합동이거나 애초에 $$ a^{ q} \equiv 1 \pmod{p} $$ 일 것이다. 따라서 $n = 2^{k} q +1 $ 이 소수면 $a^{q} \equiv 1 \pmod{n}$ 이거나 적어도 하나의 $0 \le i \le (k-1)$ 에 대해 $$ a^{2^{i} q} \equiv -1 \pmod{n} $$ 이다. 마지막으로 대우법에 의해 증명이 끝난다.
■
코드
다음은 밀러-라빈 판정법을 R 로 구현한 것으로, 계산을 위해 연속제곱법과 유클리드 호제법이 쓰였다.
FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
i<-0
if (power<0) {
while((base*i)%%mod != 1) {i=i+1}
base<-i
power<-(-power)}
if (power==0) {return(1)}
if (power==1) {return(base%%mod)}
n<-0
while(power>=2^n) {n=n+1}
A<-rep(1,n)
A[1]=base
for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
for(i in n:1) {
if(power>=2^(i-1)) {power=power-2^(i-1)}
else {A[i]=1} }
for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
return(A[1])
}
gcd <- function(a, b) {
if (b>a) {i=b; b=a; a=i;}
while(b) {
temp = b
b = a %% b
a = temp
}
return(a)
}
MR.test<-function(n)
{
q=n-1
k=0
while(!q%%2) {q=q/2; k=k+1+6}
for(i in 2:(n-1))
{
if (gcd(i,n)!=1) {return(paste(i,"is a Miller-Rabin witness!"))}
A=FPM(i,q,n)
a=A
for(j in 0:(k-1))
{
if( a==(n-1) )
{
j=0
break
}
a=(a^2)%%n
}
if (j==(n-1) & A != 1) {return(paste(i,"is a Miller-Rabin witness!"))}
}
paste(n,"passes the Miller-Rabin test!")
}
MR.test(17)
MR.test(121)
MR.test(341) #Almost composite yields fermat witness 2, but 341=11*31 doesn't.
MR.test(561) #Carmicheal number 56 = 3*11*17
MR.test(1031) #1031 is a prime
MR.test(1105) #Carmicheal number 1105 = 5*13*17
MR.test(1729) #Carmicheal number 1729 = 7*13*19
MR.test(41041) #Carmicheal number 41041 = 7*11*13*41
다음은 코드를 실행시킨 결과다.
밀러-라빈 판정법은 페르마 판정법과 달리 카마이클 수인 $561$, $1105$, $1729$, $41041$ 도 잡아내는 걸 알 수 있다.
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p137. ↩︎