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

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

AKSアルゴリズムとは? 史上初の多項式時間素数判定アルゴリズム
それってすごいことなの? コンピュータ・サイエンスの計算量理論おける画期的発見です
PRIMES is in P とは? AKSアルゴリズムが発表された論文名 (2002年8月発表)
発表者は? インド工科大学 (A)アグラワル教授 (K)カヤル氏 (S)サクセナ氏
このサイトは? AKSアルゴリズム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 セクション3の解説
    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 セクション4の解説  NEW!
    1. 有用な素数の存在の証明
      1. Lemma 4.2.
    2. nが素数の場合の証明
      1. Lemma 4.3.
    3. nが合成数の場合の証明
      1. Lemma 4.4.
      2. Lemma 4.5.
      3. Lemma 4.6.
      4. Lemma 4.7.
  7. 多項式時間アルゴリズムであることの証明
    1. Theorem 5.1.

ABSTRACT

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


ごあいさつ

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


更新履歴

折をみて内容の改善、追加をおこなっていくつもりですので、ご期待下さい。
ご意見、誤り等の指摘は下記メールアドレス宛てにお願いします。
Takeshi Aoyama ch_bleue@y7.dion.ne.jp