ミラー–ラビン素数判定法

ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法やソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。

概念

フェルマーやソロベイ–シュトラッセンの素数判定法と同様、ミラー–ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。

まず、有限体 $\mathbb {F} _{p}\left(=\mathbb {Z} /p\mathbb {Z} \right)$ の単位元の平方根についての補題を考える。ここで、p は奇素数である。p を法とした剰余（mod p）において、1と-1の二乗は常に1となる。これらを 1 の「自明な」平方根と呼ぶ。p は素数なので 1 の「自明でない」平方根は存在しない。これを示すため、1 mod p の非自明な平方根を x とする。このとき、以下が成り立つ:

x^{2}\equiv 1{\pmod {p}}

x^{2}-1\equiv 0{\pmod {p}}

\left(x-1\right)\left(x+1\right)\equiv 0{\pmod {p}}

pは素数なので、これは $x-1$ または $x+1$ が pで割り切れることを示す。一方、x は 1 でも -1 でもないので(mod p)、 $x-1$ も $x+1$ も p で割り切れない。すなわち、二乗して 1 (mod p）となるのは、1 および -1 だけということになる。

さて、n を 奇素数とするが、一般に n > 2 の奇数の性質として、n − 1 を $2^{s}\cdot d$ と表現できる。ここで s は正整数で、d は奇数である。つまり、d は n − 1 を繰り返し 2 で割った結果と同じである。すると、全ての $a\in \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}$ について:

a^{d}\equiv 1{\pmod {n}}

または、ある $0\leq r\leq s-1$ に対して

a^{2^{r}\cdot d}\equiv -1{\pmod {n}}

が成立する。

これら合同式のいずれかが真となることを示すため、以下のフェルマーの小定理を利用する:

a^{n-1}\equiv 1{\pmod {n}}

ここで、

a^{n-1}=a^{2^{s}\cdot d}\equiv 1{\pmod {n}}

であるから、この平方根は上述の補題から 1 または −1 （mod n）である。−1 の場合は後者の合同式が成り立つ。

1 の場合はさらに平方根を考えていくと、上述の補題から 1 または −1 （mod n）となる。一度も −1 （mod n）とならないまま、r = 0 となったとする。

a^{2^{0}\cdot d}=a^{d}\equiv 1{\pmod {n}}

この場合後者の合同式は成立せず、前者の合同式が成立する。

ミラー–ラビン素数判定法は上記の主張の対偶に基づいている。すなわち、整数 n に対し、以下が成り立つ a を見つけたとする。

a^{d}\not \equiv 1{\pmod {n}}

かつ、任意の $0\leq r\leq s-1$ に対して

a^{2^{r}d}\not \equiv -1{\pmod {n}}

すると、n は合成数であり、a は n の合成性の証拠（証人）である。証拠とならない a を「強い嘘つき; strong liar」と呼び、n を底 a についての「強擬素数; strong pseudoprime」と呼ぶ。「強い嘘つき」とは、n が合成数であるのに合同式が成立することによって素数であると嘘をつくことから来ている。

奇数の合成数には、多くの証拠（証人）a がある。しかし、そのような a を生成する単純な方法は知られていない。ミラー–ラビン素数判定法では、 $a\in \left(\mathbb {Z} /n\mathbb {Z} \right)$ であるような数をランダムに選択し、それが n の合成性の証拠（証人）となりうるかを調べる。n が合成数なら、ほとんどの a は証拠となるので、高い確率で n が合成数であることを検出できる。しかし、不運にも n に対する「強い嘘つき」となる a を選んでしまう可能性も若干ある。この確率を減らすには、いくつかの独立に選んだ a で判定を繰り返す。

アルゴリズムと実行時間

このアルゴリズムは次のように表現される:

入力:

n>1

: 素数判定対象の奇数の整数;

k

: 判定の正確度を指定するパラメータ

出力:

n

が合成数なら composite、さもなくば probably prime

n-1

を 2 のべき乗で割って、

2^{s}\cdot d

の形式にする。

以下を

k

回繰り返す:

[

1,n-1\

] の範囲から

a

をランダムに選ぶ。

a^{d}\neq 1\ {\bmod {\ }}n

で、かつ

[0,s-1\

] の範囲の全ての

r

について

a^{{2^{r}}d}\ {\bmod {\ }}n\neq \ -1

なら、composite を返す。

probably prime を返す。

平方の繰り返しをべき剰余を使って実現すると、このアルゴリズムの実行時間は O(k × log³ n) となる。ここで、k は異なる a で判定を行う回数である。以上から、このアルゴリズムが多項式時間の効率のよいアルゴリズムであることがわかる。FFTベースの乗算によって実行時間を Õ(k × log² n) まで抑えることができる。

コード例

以下に Ruby での本アルゴリズムの実施例を示す。

  class Integer
    def prime?
      n = self.abs()
      return true if n == 2
      return false if n == 1 || n & 1 == 0
      d = n-1
      d >>= 1 while d & 1 == 0
      20.times do                               # 20 は上の説明の k に相当
        a = rand(n-2) + 1
        t = d
        y = ModMath.pow(a,t,n)                  # 実装コードは下にある
        while t != n-1 && y != 1 && y != n-1
          y = (y * y) % n
          t <<= 1
        end
        return false if y != n-1 && t & 1 == 0
      end
      return true
    end
  end
  
  module ModMath
    def ModMath.pow(base, power, mod)
      result = 1
      while power > 0
        result = (result * base) % mod if power & 1 == 1
        base = (base * base) % mod
        power >>= 1;
      end
      result
    end
  end

判定の正確度

より多くの a で判定を行えば、正確度が高くなる。任意の奇数の合成数 n について、a の少なくとも 3/4 が合成性の証拠となることがわかっている。ミラー–ラビン素数判定法において n についての「強い嘘つき」となる数の集合は、ソロベイ–シュトラッセン素数判定法で嘘つきとなる数の集合の部分集合であり、多くの場合は真部分集合となる。つまり、ミラー–ラビン素数判定法はソロベイ–シュトラッセン素数判定法よりも強力である。n が合成数なのに素数の可能性があると判定してしまう確率は最大で $4^{-k}$ である。一方、ソロベイ–シュトラッセン素数判定法では最大 $2^{-k}$ となる。

合成数を素数に間違ってしまう平均確率は $4^{-k}$ よりずっと小さい。Damgård、Landrock、Pomeranceはこの値を正確に求めたことがある。しかし、そのような確率は素数を生成する際には利用できるが、素性の知れない数の素数判定には依存すべきでない。特に暗号では敵が素数を強擬素数にすり替える可能性を考慮しなくてはならない。従って、 $4^{-k}$ という確率だけを信用すべきである。

決定的アルゴリズム

ミラー–ラビン素数判定法は、Gary L. Miller が最初に開発したMillerテストをマイケル・ラビンが無条件の確率的アルゴリズムに修正したものである。元となったMillerテストはある限度以下の全ての a を調べるという、未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムである。とはいえ拡張リーマン予想全体を必要とするわけではなく、平方ディリクレ指標について拡張リーマン予想が成り立てばよい。

Millerテストは未証明の拡張リーマン予想を必要としていることや、それを修正したミラー–ラビン素数判定法が許容出来る誤判定確率から判定時間を調整でき速度面で有利であることから実際には使われていない。また同じく決定的アルゴリズムであるAKS素数判定法の方が、証明されていない予想に依存していないぶんだけMillerテストよりも強い。

Millerテストには、判定を信頼できるものにするには限度をどう決めたらよいかという問題がある。

判定対象の数 n が合成数なら、n と互いに素な「強い嘘つき」の a は群 $\left(\mathbb {Z} /n\mathbb {Z} \right)^{*}$ の真の部分群に含まれる。つまり $\left(\mathbb {Z} /n\mathbb {Z} \right)^{*}$ の生成元集合の全 a について判定するとき、その中には必ず n の合成性の証拠となる数が含まれる。拡張リーマン予想が真であると仮定すると、ミラーが既に指摘したように O((ln n)²) より小さい元から、この集合が生成されることがわかっている。big O記法の定数は Eric Bach によって 2 まで減らされた（1990年）。このことから、次のような素数判定アルゴリズムが導かれる:

入力: n > 1; 判定対象の奇数

出力: n が合成数なら composite、さもなくば prime を返す。

n-1

を 2 のべき乗で割って、

2^{s}\cdot d

の形式にする。

以下を

[2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]

の範囲の全ての a について繰り返す:

a^d mod n ≠ 1 かつ [0, s − 1] の範囲の全ての r について

a^{d\cdot 2^{r}}

mod n ≠ −1 なら、composite を返す。

prime を返す。

このアルゴリズムの実行時間は Õ((log n)⁴) である。

判定対象の数 n が十分小さければ、全ての a < 2(ln n)² を調べる必要はなく、もっと小さい証拠の可能性のある数の集合で十分である。例えば、Jaeschke (1993) は以下を検証した。

もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。
もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である。

もちろん、a < n の場合だけ調べる。この種の基準については [1] を参照されたい。このような結果を活用することで、ある範囲の数については非常に高速で決定的な素数判定が可能である。

しかし、全ての合成数についてはこのような有限の集合では不十分である。Alford、Granville、Pomerance は、合成数 n について合成性の証拠となる最小の数が $(\ln n)^{1/(3\ln \ln \ln n)}\;$ より大きい合成数が無数に存在する、X が十分大きいときには X 以下のそのような合成数の個数は少なくとも $X^{1/(35\ln \ln \ln X)}$ であることを示した。また彼らはヒューリスティック的に、w 以下の合成性の証拠となる数のある n 以下の合成数について w のオーダーを $\Theta (\ln n\,\ln \ln n)$ であると示唆した。

参考文献

W. R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses, in: Algorithmic Number Theory, First International Symposium, Proceedings (L. M. Adleman, M.-D. Huang, eds.), LNCS 877, Springer-Verlag, 1994, pp. 1–16. Carl Pomerance, List of Papers, 96.
Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, pp. 355–380.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 890–896 of section 31.8, Primality testing.
I. Damgård, P. Landrock and C. Pomerance (1993), Average case error estimates for the strong probable prime test, Math. Comp. 61(203) p.177–194.
Gerhard Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation 61 (1993), no. 204, pp. 915–926.
Gary L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12 (1980), no. 1, pp. 128–138.
René Schoof, Four primality testing algorithms, to appear in: Surveys in algorithmic number theory, Cambridge University Press. PDF