https://pydocument.hatenablog.com/entry/2023/03/24/231507

ミラー-ラビン素数判定法は、与えられた数が素数であるかどうかを判定するアルゴリズムの一つです。この判定法は確率的アルゴリズムであり、高速に動作します。この記事では、この素数判定法の概要とPythonでの実装方法を解説します。

ミラー-ラビン素数判定法の概要

ミラー-ラビン素数判定法は以下のステップで素数を判定します。

判定したい数 n が 2 以下の場合、n が 2 なら素数、それ以外は素数ではない
n が偶数の場合、n は 2 以外の偶数なので、合成数である
n が奇数の場合、n - 1 を 2^r * d（d は奇数）の形に分解する
以下のいずれかの条件を満たす場合、n は素数である可能性が高いと判定する（下記の式を満たした場合は合成数ではない）
- a^d ≡ 1 (mod n)
- a^{(2^s * d)} ≡ -1 (mod n) (0 ≤ s ≤ r - 1)

上記の a には乱数を使用します。このテストを複数回繰り返すことで、判定の精度を高めることができます。

誤判定について

ミラーラビン素数判定法は確率的なアルゴリズム（乱数などを利用して動作するため、同じ入力に対しても結果が変わる可能性があるアルゴリズム）です。誤判定の可能性は低いですが、100% 正確な結果を保証するものではありません。擬似素数と呼ばれる、合成数であるにも関わらず、素数と判定される数が存在します。

Python での実装例

以下に、Python でミラー-ラビン素数判定法を実装する例を示します。

サンプルコード

まずは、必要最低限のシンプルなコードです。

import random

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

    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    # 乱数の試行回数を指定します
    k = 20
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False

    return True

2 以下の数値、および偶数は事前に除外して判定を効率化しています。
n-1 を 2^r * d に分解する処理では、while ループを用いて d が奇数になるまで 2 で割り続け、その回数を r に記録しています。
乱数 a は 2 から n-2 の範囲から選択しています。
pow(a, d, n) は a^d を n で割った余りを効率的に計算します。
内側の for ループでは、x を繰り返し2乗し、n-1 と比較することで、合成数であるかを判定します。

試行回数の変更

このコードでは、k の値を変えることで、素数判定の試行回数を変更できます。

# 試行回数を変更する例
k = 10  # 試行回数を10回にする場合

多数の数値を素数判定する場合

多数の数値を素数判定する処理を、関数化して簡潔に利用できるようにします。

import random

def _try_composite(a, d, n, r):
    if pow(a, d, n) == 1:
        return False
    for i in range(r):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n は確実に合成数

def is_prime(n, k=20):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    for _ in range(k):
        a = random.randint(2, n - 2)
        if _try_composite(a, d, n, r):
            return False
    return True

def find_primes(numbers):
    """
    与えられた数値リストに対して素数判定を行う関数

    Args:
      numbers: 素数判定を行う数値のリスト
    Returns:
      素数のリスト
    """
    primes = []
    for number in numbers:
        if is_prime(number):
            primes.append(number)
    return primes

# 使用例
numbers = [11, 29, 89, 100, 149, 201, 523]
prime_numbers = find_primes(numbers)
print("素数のリスト:", prime_numbers)

まとめ

ミラー-ラビン素数判定法は、高速でありながら比較的高い精度で素数判定を行うことができるアルゴリズムです。Python の pow() 関数を使うことで、効率的に実装できます。確率的アルゴリズムであるため100% 正確な結果を保証するものではないことに注意する必要があります。ただし、試行回数を増やすことで精度を高められます。

他の素数判定法に関する説明も記事にしています。

pydocument.hatenablog.com