ミラー・ラビン素数判定法：2⁶⁴までの数にどう適用されるか

高速で信頼性の高い素数判定アルゴリズムの深掘り

ハイライト

ミラー・ラビン素数判定法は、与えられた数が素数であるかを確率的に判定する高速なアルゴリズムです。
2⁶⁴までの数に対しては、特定の基数セットを用いることで、実質的に決定的な素数判定が可能です。
この判定法は、RSA暗号などの公開鍵暗号システムで大きな素数を生成する際に重要な役割を果たします。

ミラー・ラビン素数判定法とは？

ミラー・ラビン素数判定法（Miller–Rabin primality test）は、与えられた正の整数が素数であるかどうかを判定するための確率的アルゴリズムです。これは、ギャリー・ミラーによって開発されたミラーテストを、マイケル・ラビンが無条件の確率的アルゴリズムに修正したものです。フェルマーの素数判定法やソロベイ–シュトラッセン素数判定法と同様に、素数に関して成り立つ等式に基づいて判定を行います。

素数を判定する基本的な方法として、与えられた数 \(N\) を \(2\) から \(\sqrt{N}\) までの数で順に試し割りしていく方法がありますが、これは \(O(\sqrt{N})\) の計算量となり、非常に大きな数に対しては非現実的です。一方、ミラー・ラビン素数判定法は、より高速に素数判定を行うことができます。

アルゴリズムの基礎

ミラー・ラビン素数判定法は、フェルマーの小定理から派生した考え方に基づいています。フェルマーの小定理は「\(p\) が素数であり、\(a\) が \(p\) と互いに素な自然数であるならば、\(a^{p-1} \equiv 1 \pmod{p}\) が成り立つ」というものです。しかし、この逆は真ではなく、フェルマーテストを通過しても合成数であるようなカーマイケル数のような数が存在します。

ミラー・ラビンテストは、このフェルマーテストを強化したものです。判定したい奇数 \(n\) に対して、\(n-1 = 2^s \cdot d\) （\(d\) は奇数）と分解します。そして、\(1 < a < n-1\) となるランダムな整数 \(a\)（これを「証拠」または「基数」と呼びます）を選び、以下の条件を確認します。

\[ a^d \equiv 1 \pmod{n} \] または \[ a^{2^r d} \equiv -1 \pmod{n} \quad \text{for some } 0 \le r < s \]

もし、これらの条件のどちらも満たされない場合、\(n\) は合成数であることが確定します。どちらかの条件を満たす場合、\(n\) は「\(a\) を基数とする強い擬素数」と呼ばれ、素数である可能性が高いと判断されます。

確率的な性質

ミラー・ラビン素数判定法は確率的アルゴリズムであり、検定に合格した数が素数である確率は高いですが、合成数を誤って素数と判定してしまう可能性（擬素数）がゼロではありません。ただし、合成数 \(n\) に対して、ランダムに選ばれた基数 \(a\) が \(n\) の合成性の証拠とならない確率は最大で \(1/4\) です。したがって、異なる複数の基数 \(a\) でテストを行い、全てに合格した場合、その数が素数である確率は非常に高くなります。\(k\) 個の独立したランダムな基数でテストを行い、全てに合格した場合、合成数を素数と判定する確率は最大で \((1/4)^k\) となります。

2⁶⁴までの数への適用

一般的にミラー・ラビン素数判定法は確率的ですが、判定する数の範囲がある程度以下であれば、特定の基数セットでテストするだけで決定的な判定が可能であることが知られています。これは、その範囲内の全ての合成数に対して、指定された基数セットの少なくとも1つが合成性の証拠となることが数学的に証明されているためです。

Miller-Rabinテストの概念図（イメージ）

2⁶⁴までの決定性

特に、64ビット整数（2⁶⁴未満の数）に対しては、いくつかの研究によって特定の限られた基数セットでミラー・ラビンテストを行うことで、確率的ではなく決定的に素数判定ができることが示されています。例えば、2⁶⁴未満の数であれば、基数として2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 の12個の素数を使用することで、その数が素数か合成数かを確実に判定できることが知られています。

以下の表は、判定する数の上限に対して、決定的な判定に必要な基数セットの例を示しています。

判定する数の上限	必要な基数セット
2³²未満	2, 7, 61
2⁴⁸未満	2, 3, 5, 7, 11, 13, 17
2⁶⁴未満	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

このように、2⁶⁴までの数に対しては、これらの固定された基数セットでテストを行うことで、非常に高速かつ確実に素数判定を行うことができます。これは実用上、特に大きな数の素数判定が必要とされる暗号理論などの分野で非常に重要です。

実装における考慮事項

ミラー・ラビン素数判定法を実装する際には、効率的なモジュラ冪乗（\(a^b \pmod{n}\) の計算）が不可欠です。Pythonには pow(a, b, n) のようにこの計算を効率的に行う組み込み関数があります。


def power(a, b, m):
    res = 1
    a = a % m
    while b > 0:
        if b % 2 == 1:
            res = (res * a) % m
        a = (a * a) % m
        b //= 2
    return res

def miller_rabin_test(n, a):
    # n-1 = 2^s * d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    x = power(a, d, n)

    if x == 1 or x == n - 1:
        return True

    for _ in range(s - 1):
        x = power(x, 2, n)
        if x == n - 1:
            return True
        if x == 1:
            return False # Composite

    return False # Composite

def is_prime_miller_rabin(n):
    if n <= 1: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False

    # Bases for deterministic test up to 2^64
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in bases:
        if n == a: return True
        if not miller_rabin_test(n, a):
            return False
    return True # Probably prime, but deterministic for n < 2^64

# Example usage:
# print(is_prime_miller_rabin(17)) # True
# print(is_prime_miller_rabin(9))  # False

上記のPythonコードは、2⁶⁴までの数に対して決定的なミラー・ラビン素数判定を行うための基本的な構造を示しています。指定された基数セットに対してmiller_rabin_test関数を繰り返し呼び出し、いずれかのテストに失敗すれば合成数と判定します。全てのテストに合格すれば、2⁶⁴までの範囲であれば素数と判定できます。

他の素数判定法との比較

素数判定法には、試し割り法、エラトステネスの篩、フェルマーテスト、ソロベイ–シュトラッセン素数判定法など様々なものがあります。それぞれの方法は、判定できる数の大きさや計算速度、結果の確実性において特徴があります。

様々な素数判定法の比較（イメージ）

試し割り法

最も単純な方法ですが、大きな数に対しては非常に時間がかかります。計算量は \(O(\sqrt{N})\) です。

エラトステネスの篩

これは、ある数までの全ての素数をリストアップするのに効率的な方法です。単一の数の素数判定には向いていません。計算量は約 \(O(N \log \log N)\) です。

フェルマーテスト

ミラー・ラビンテストの基となった確率的テストですが、カーマイケル数のような問題点があります。計算量は \(O(\log N)\) の冪乗計算に依存します。

AKS素数判定法

これは、2002年に発見された多項式時間で動作する決定的な素数判定アルゴリズムです。理論的には重要ですが、実用上の速度はミラー・ラビン法に劣る場合があります。計算量は \(O(\log^{6} N)\) またはそれ以上です。

ミラー・ラビン素数判定法は、確率的アルゴリズムでありながら高速であり、特に特定の範囲（例：2⁶⁴まで）では決定的な判定が可能であるため、実用上非常に広く用いられています。

応用分野

ミラー・ラビン素数判定法は、その効率性と信頼性から様々な分野で応用されています。最も顕著なのは暗号理論です。

暗号理論

公開鍵暗号システム、特にRSA暗号では、非常に大きな素数を生成する必要があります。素数判定は、生成された候補となる数が実際に素数であるかを確認するために不可欠なプロセスです。ミラー・ラビン素数判定法は、大きな数の素数性を高速かつ高い信頼性で判定できるため、RSA鍵生成において中心的な役割を果たしています。