エディックスン-レフラム素数判定法を利用した素数判定プログラムをPythonで実装する

エディックスン-レフラム素数判定法は、素数を判定するアルゴリズムの一つで、比較的高速であることが特徴です。このアルゴリズムは、以下の手順で素数を判定します。

判定する数nが2以下の場合は、nが素数であると判定する。
nが2の倍数の場合は、nが合成数であると判定する。
nが奇数の場合は、nを(2^r)×d+1の形に変換する。ただし、dは奇数で、rは0以上の整数である。このとき、dはn-1を割り切る最大の整数である。
2から10までの整数aをランダムに選び、a^d mod nを計算する。この値が1またはn-1であれば、nが素数であると判定する。そうでなければ、rが0からr-1までの各値について、(a^{2^r}×d) mod nを計算する。いずれかの値がn-1であれば、nが素数であると判定する。そうでなければ、nが合成数であると判定する。

pydocument.hatenablog.com

Pythonでの実装

以下に、Pythonで実装したエディックスン-レフラム素数判定法のコードを示します。

import random

def is_prime(n):
    if n <= 2:
        return n == 2
    if n % 2 == 0:
        return False
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(10):
        a = random.randint(2, n - 1)
        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

この実装では、まずnが2以下の場合や2の倍数の場合は、素数でないと判定します。それ以外の場合には、n-1をd×2^rの形に変換します。そして、ランダムに選んだ整数aに対して、a^d mod nを計算します。これが1またはn-1であれば、素数である可能性が高いと判定します。それ以外の場合には、2からr-1までの各値について、a^{2^r}×d mod nを計算していきます。どれもn-1でなければ、nは合成数であると判定します。この実装では、forループの範囲を10回としています。これは、aをランダムに選ぶことで判定の正確性を高めるためです。なお、10回程度の繰り返しで正確な判定が得られることが実験的に示されています。

また、pow()関数を用いて冪剰余を計算しています。pow()関数は、pow(a, b, m)のように3つの引数を取り、aのb乗をmで割った余りを計算する関数です。この関数は、冪剰余の計算に最適化されているため、高速に処理ができます。

以上が、Pythonでのエディックスン-レフラム素数判定法の実装についての説明です。この実装では、ランダムな整数を用いた確率的な素数判定法を採用しているため、正確性は100%ではありません。しかし、高速な処理ができるため、素数の大量判定には適しています。

pydocument.hatenablog.com