AKS素数判定法

AKS素数判定法

AKS素数判定法（AKSそすうはんていほう）は、特定の自然数が素数であるかを判定するための画期的なアルゴリズムです。これは、決定的に多項式時間で素数を判定できる初の例として知られています。素数判定法が「多項式時間」であるというのは、与えられた自然数 n が素数であるかどうかを判定するのにかかる計算時間が、log(n) の多項式で上限されることを意味します。

このアルゴリズムは、2002年8月6日に発表された論文「PRIMES is in P」により知られるようになりました。著者はインド工科大学のマニンドラ・アグラワル教授と、その学生であるニラジュ・カヤル、ナイティン・サクセナの三人です。

背景

AKS素数判定法が発表される前にも多数の素数判定法が存在しましたが、リーマン予想などの未解決の仮説に依存せずに多項式時間で判定できる手法はありませんでした。AKS素数判定法の登場は、素数判定という数学的な重要問題が実際に計算クラス P に属することを示した点で、理論的には大きな成果となりました。しかし、実用面では多項式の次数が高いため、非常に大きな素数の判定においては依然として従来の判定法に劣ります。

アルゴリズムの発想

AKS素数判定法は、フェルマーテストの改良と考えられます。フェルマーの小定理に基づき、与えられた自然数 n が合成数であるときには、a が n と互いに素であれば、次の条件が成り立ちます。

$$
a^n
ot o a ext{（mod } n)
$$

この条件を改良することで、合成数をより厳密に判断することが可能になりました。さらに、AKSアルゴリズムは、確率的方法を取り入れつつ、この条件を必要十分条件として評価できる点が特徴です。

アルゴリズム概要

1. 2以上の自然数 n を入力。
2. n が累乗数であれば、「合成数」と判定して終了する。
3. n の位数が十分大きい法 r を求め、r が存在するかを確認。
4. a を r まで動かし、特定の条件が成り立たない場合は「合成数」と判定。
5. 値の評価を行い、合成数か素数かを判定する。全ての条件を満たせば「素数」と出力。

このアルゴリズムは、効率的に素数か合成数かを判断するためのもので、最悪の場合でも log(n) を基準に稼働します。特に、正確な評価を行うためには、十分な数の a を用いて評価を行う必要があります。これにより、合成数による誤判定を避けることが可能になります。

計算量

AKSアルゴリズムの時間的計算量は、$ ilde{O}(log(n)^{7.5})$ とされており、さらに改良により、$ ilde{O}(log(n)^{6})$ に到達する可能性があります。計算の各ステップにコンピュータサイエンスの手法を応用することで、より効率的な判定が実現されることが期待されています。

結論

AKS素数判定法は、理論と実用の架け橋を成す素数判定の重要なアルゴリズムであり、今後の研究においてもさらなる発展が期待されるものです。

もう一度検索