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

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

ミラー–ラビン素数判定法（またはラビン–ミラー素数判定法）は、与えられた数が素数であるかを判断するための確率的なアルゴリズムの一つです。この方法は、その性能と信頼性から広く用いられています。

アルゴリズムの背景

この判定法は、最初にGary L. Millerによって開発され、後にマイケル・ラビンによって確率的な形式に修正されました。元のMillerテストは拡張リーマン予想に依存していたため未証明の理論に基づいていましたが、ミラー–ラビン法は実用的なアルゴリズムとして評価され、現在も盛んに利用されています。

基本的な考え方

ミラー–ラビン素数判定法は、数論における群の性質を活用します。与えられた奇数n（n > 1）の性質を調べ、特定の条件が満たされない場合には、nが合成数であると判定します。このために、n-1を2のべきで分解し、いくつかの条件を満たすランダムな整数aを選びます。

1. n-1は、形 `2^s d` で表される。
2. 選んだ整数aを使って以下の条件を確認する。
- `a^d ≡ 1 (mod n)` であるか、または
- `a^{2^r d} ≡ -1 (mod n)` が成立する。

これらの条件が成立しない場合、nは合成数であると判断されます。

実行の流れ

以下の手順でアルゴリズムが実行されます：
1. 判定対象の奇数nに対して、k回の試行を指定します。
2. n-1を2のべき乗で割り、`2^s d`の形に変形します。
3. 1からn-1の範囲からランダムに整数aを選出します。
4. `a^d`が1に等しくないことを確認し、全てのrについて`a^{2^r d}`が−1に等しくないことも確認します。
5. 条件が成り立たなければ、nは合成数として「composite」と返します。そうでない場合には、「probably prime」と返されます。

このアルゴリズムの実行時間は、O(k × log³n)とされており、kは試行の回数を示します。実装時には、平方剰余の計算を効率化するために、素早い乗算手法を適用することが可能です。

判定の精度

kの数を増やすことで判定の精度を高めることができます。特に、奇数の合成数に対しては、少なくとも3/4の確率でaが合成性の証拠となることが知られています。誤って素数と判定される確率は最大で`4^{-k}`となります。これは、判断を誤った場合に、合成数の特定性をより確実にするためにも重要です。

ミラー–ラビン法は、特定の条件を満たさない場合には、確実に合成数を見つけ出すことができますが、合成数であるのに素数と誤認されるケース（強擬素数）にも留意しなければなりません。

サンプルコード

以下は、Rubyでの基本的な実装例です。

```ruby
def miller_rabin(n, k)
return false if n < 2
return true if n == 2

s = 0
d = n - 1
while d.even?
s += 1
d /= 2
end

k.times do
a = rand(2..n-2)
x = pow_mod(a, d, n)
next if x == 1 || x == n - 1

(0...(s - 1)).each do
x = pow_mod(x, 2, n)
return false if x == 1
return true if x == n - 1
end
return false
end
true
end
```

まとめ

ミラー–ラビン素数判定法は、確率的で効率的な素数判定の手法として有力です。誤判定があるものの、実務の上では非常に利用価値があります。特に暗号理論において、素数生成における応用が期待されています。

もう一度検索