素数判定

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

素数判定(そすうはんてい)とは、ある自然数 n素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。

RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。

仮定なしで決定的かつ多項式時間で終了する(クラスPに含まれる)素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された(AKS素数判定法)。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はAPR判定法英語版などのほうが高速であることが多い。

なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。

確率的素数判定法[編集]

素数判定法の中には確率的アルゴリズムに基づいた、与えられた自然数 n を「合成数である」または「良く分からない」と判別する判定法がある。この判定法を確率的素数判定法 (probabilistic primality test) ということがある。これに対して「素数である」あるいは否と判定する決定的アルゴリズムは決定的素数判定法 (deterministic primality test) ということがある。

「合成数である」と判定した場合には、nは合成数であると確定するが、「良く分からない」と判断した場合には、それだけではあまり有用な情報は得られない。しかし、判定を適当な回数だけ繰り返し、その間一度も「合成数である」と出力されないならば、その n は素数である見込みが大きいと言える。このようにして得られた「素数ではないかと思われる数」のことを確率的素数 (probable prime) という。

一般に確率的素数判定法は、決定的素数判定法よりもはるかに高速であるので、実用上は確率的素数判定法の繰り返しをもって素数判定法に代える場合も多い。

また、ミラー–ラビン素数判定法はある種の一般化されたリーマン予想のもとでは多項式時間で動く素数判定法として動作することが知られている。

様々な判定法[編集]

プログラム例[編集]

Pythonによる素数判定(試し割り)のプログラム例を示す。

import math


def is_prime(n):
    if n <= 1:
        return False

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    for i in range(3, math.ceil(math.sqrt(n)), 2):
        if n % i == 0:
            return False

    return True

この例は入力nが素数である場合はTrueを返し、それ以外の場合はFalseを返す。

Pythonによる素数判定(エラトステネスの篩)のプログラム例を示す。

import math


def eratosthenes(n):
    list_prime = list(range(2, n))

    for i in range(2, n):
        if i in list_prime:
            for j in range(i * 2, n, i):
                if j in list_prime:
                    list_prime.remove(j)

        if i > int(math.sqrt(n)):
            break

    return list_prime

この例は入力nまでの素数のリストを返す。