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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 概念

フェルマーや Solovay-Strassen の素数判定法と同様、ミラー-ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。

まず、有限体 $\mathbb{Z}_p$ の単位元の平方根の補題を考える。ここで、p は素数である。1 について p を法とした剰余（mod p）の平方根は 1 および -1 となる。これらを 1 の「自明な」平方根と呼ぶ。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}$

x は 1 または -1 と p を法として合同ではないので、 $x - 1$ も $x + 1$ も p で割り切れない。しかし素数が2つの整数のいずれも割り切れないなら、その積も割り切れないはずである。すなわち、二乗して 1 (mod p）となるのは、1 および -1 だけということになる。

さて、n を奇素数としたとき、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}$

または

$a^{2^r\cdot d} \equiv -1\pmod{n}$ ここで $0 \le r \le s-1$

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

$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 \not\equiv -1\pmod{n}$

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

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

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

かつ

$a^{2^rd} \not\equiv -1\pmod{n}$ ここで $0 \le r \le s-1$

すると、a は n の合成性の証拠（証人）である。これが成り立たない a を「強い嘘つき; strong liar」と呼び、n を底 a についての「強擬素数; strong probable prime」と呼ぶ。「強い嘘つき」とは、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 \ne 1\ \bmod\ n$ で、かつ $[0, s - 1\$ ] の範囲の全ての

r

について $a^{{2^r}d}\ \bmod\ n \ne\ -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 についての「強い嘘つき」となる数の集合は、Solovay-Strassen素数判定法で嘘つきとなる数の集合の部分集合であり、多くの場合は真部分集合となる。つまり、ミラー-ラビン素数判定法は Solovay-Strassen素数判定法よりも強力である。n が合成数なのに素数の可能性があると判定してしまう確率は最大で $4 - k$ である。一方、Solovay-Strassen では最大 $2 - k$ となる。

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

[編集] 決定的アルゴリズム

ミラー-ラビン素数判定法は、ある限度以下の全ての a を調べるという決定的アルゴリズムにすることもできる。判定を信頼できるものにするには限度をどう決めたらよいかという問題がある。

判定対象の数 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,\lfloor2(\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)⁴) である。この判定法の正しさを証明するには拡張リーマン予想全体を必要とはしない。平方ディリクレ指標について拡張リーマン予想が成り立てばよい。

このアルゴリズムは実際には使われていない。というのも乱択アルゴリズムのミラー-ラビン素数判定法より性能が悪いためである。理論的には、AKS素数判定法は証明されていない予想に依存していないぶんだけこのアルゴリズムよりも強い。

判定対象の数 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 / (35lnlnln 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

[編集] 外部リンク

カテゴリ: 数論 | 数論アルゴリズム

See also ebooksgratis.com: no banners, no cookies, totally FREE.