📂整数論

ミラー・ラビン判定法

定理¹

奇数$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$も捕まえられることがわかる。