素数判定法

ウィキペディア

素数判定

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/10 07:26 UTC 版)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "素数判定" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年1月)

素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。

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

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

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

確率的素数判定法

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

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

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

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

計算複雑性

計算複雑性理論では、ある数が素数かどうかを判定する問題はPRIMESと表記される。PRIMESがco-NPであることは簡単に示すことができる。なぜなら、その補問題であるCOMPOSITE（ある数が合成数であるかどうかを判定する問題）は、任意の数に対し、問題の数がそれで割り切れるかどうかの確認が多項式時間で行えることよりNPに属するからである。

1975年にVaughan PrattはPRIMESがNPに、また従ってNP ∩ co-NPに属することを示した（Primality certificateを参照）。

Solovay-StrassenとMiller-RabinによるアルゴリズムによりPRIMESはco-RPに属することが判明した。1992年にはAdleman-HuangによるアルゴリズムがZPP = RP ∩ co-RPまで複雑性を下げ、Prattによる結果を更新した。^[1]

1983年に発見されたAdleman–Pomerance–Rumelyによる素数判定法によりPRIMESはQPに属することが判明したが、これと上記の結果との関係は分かっていない。

その実際上の扱いやすさや、リーマン予想に基づく多項式時間アルゴリズムの存在、その他の類似の状況証拠により、素数判定は多項式時間でおこなえると長く信じられてきたが、証明はできなかった。AKS素数判定法が最終的にこの長年の問題に終止符を打ち、PRIMESがPに属することを証明した。しかしながら、PRIMESがP-完全かどうかは分かっておらず、NCやLなどのPに含まれるクラスに属するかどうかも分かっていない。PRIMESがAC⁰に属しないことが証明されている。^[2]

様々な判定法

• 一般的な数に対する判定法
  • 決定的素数判定法
    • 試し割り法、エラトステネスの篩
    • 最大公約数
    • ウィルソンの定理
    • Millerテスト - 多項式時間アルゴリズムだが、GRHのもとで正当性が示される。
    • Adleman–Pomerance–Rumely primality test（英語版） - 高速だが、多項式時間アルゴリズムではない。
    • ECPP（英語版）
    • AKS素数判定法 - 多項式時間アルゴリズム
  • 確率的素数判定法
    • フェルマーテスト
    • ソロベイ–シュトラッセンテスト
    • ミラー–ラビン素数判定法
• 特殊な条件の数に対する判定法
  • Pocklingtonの判定法（英語版） - N = FR+1, F> sqrt(N), Fの素因数分解が既知の場合の判定法
  • リュカ・テスト - pが(4j + 3)型素数のメルセンヌ数に対する判定法
  • リュカ–レーマー・テスト - p が奇素数のメルセンヌ数に対する判定法
  • リュカ–レーマー–リーゼル・テスト
• 特殊な形の数に対する判定法
  • Prothの判定法（英語版） - プロス数に対する判定法
  • Pépinの判定法（英語版） - フェルマー数に対する判定法

プログラム例

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)) + 1, 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までの素数のリストを返す。

脚注

[脚注の使い方]

1. ^ Adleman, Leonard M.; Huang, Ming-Deh (1992). Primality testing and Abelian varieties over finite field. Lecture notes in mathematics. 1512. Springer-Verlag. ISBN 3-540-55308-8 
2. ^ E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.

ウィキペディア小見出し辞書

素数判定法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/02 03:03 UTC 版)

「メルセンヌ数」の記事における「素数判定法」の解説

知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にある[要出典]。