多項式時間素数判定アルゴリズムについて

AKSアルゴリズム PRIMES is in P 完全理解！！

ＡＫＳアルゴリズムとは？	史上初の多項式時間素数判定アルゴリズム
それってすごいことなの？	コンピュータ・サイエンスの計算量理論おける画期的発見です
PRIMES is in P とは？	ＡＫＳアルゴリズムが発表された論文名 （２００２年８月発表）
発表者は？	インド工科大学 (A)アグラワル教授 (K)カヤル氏 (S)サクセナ氏
このサイトは？	ＡＫＳアルゴリズムと PRIMES is in Pに関する解説のページです

元論分のサイト：Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P, the original version of the paper.

1. アルゴリズムの基本となるアイデア
2. アルゴリズムの概要
   1. AKS アルゴリズム
   2. 使用する用語と記号
   3. アルゴリズムの動作概要
3. アルゴリズムの正当性の証明概要
4. アルゴリズムの正当性の証明の蛇足説明
5. アルゴリズムの正当性の証明詳細のための準備 　PRIMES is in P セクション３の解説
   1. Lemma 3.1.
   2. Lemma 3.1.(fact 1)
   3. Lemma 3.1.(fact 2)
   4. Lemma 3.1.(fact 3)
   5. Lemma 3.1.(fact 4)
   6. Lemma 3.2.
   7. Lemma 3.3.
6. アルゴリズムの正当性の証明詳細 Theorem 4.1. 　PRIMES is in P セクション４の解説 　NEW!
   1. 有用な素数の存在の証明
      1. Lemma 4.2.
   2. ｎが素数の場合の証明
      1. Lemma 4.3.
   3. ｎが合成数の場合の証明
      1. Lemma 4.4.
      2. Lemma 4.5.
      3. Lemma 4.6.
      4. Lemma 4.7.
7. 多項式時間アルゴリズムであることの証明
   1. Theorem 5.1.

ABSTRACT

２００２年８月、カンプール・インド工科大学の３人の研究者、アグラワル教授とその生徒のカヤル氏、サクセナ氏によって画期的なアルゴリズム（AKSアルゴリズム）が彼らの論文 PRIMES is in P において発表されました。与えられた数が素数であるか否かを多項式時間で判定できるアルゴリズムです。多項式時間の素数判定アルゴリズムとしては史上初のものであり、コンピュータ・サイエンスの計算量理論の分野において非常に重要な意味を持つ発見です。（と偉い人たちがみんな言ってます。）

ごあいさつ

私はたまたまこの論文を詳しく読む機会がありましたのでＷＥＢ上にこの論文 PRIMES is in P とＡＫＳアルゴリズムの解説を載せてみることにしました。元の論文に沿って、アルゴリズムとその正当性の証明の概要説明を行っていく予定です。元の論文では説明が端折らているところなど埋めながら出来るだけ詳しく解説していきたいと思っています。

更新履歴

• ２００３年７月２９日：「アルゴリズムの正当性の証明詳細 Theorem 4.1.」のページを追加。（元論文の中核部です）
• ２００３年６月１８日：「使用する用語と記号」の箇所に、「条件１」かつ「条件２」⇔「条件１」かつ「条件３」の証明を追加
• ２００３年６月１６日：「アルゴリズムの正当性の証明詳細のための準備」のページを追加
• ２００３年４月３０日：「アルゴリズムの基本となるアイデア」の内容を結構更新