AKSアルゴリズム @ 素因数分解 @ IDM

最終更新日:2005.11.27 この文書は、Manindra's home pageにて公開されているPRIMES is in PのRevised paper version(3訂版)に基づいている。同論文の2005年11月27年現在の最新版はAUgust, 2005 version(6訂版) AKSアルゴリズムについての概説は、Wikipediaの項目も参照。 目次 紹介 発想 記法 アルゴリズム アルゴリズムの正当性 計算量の評価 関連資料 変更履歴 紹介 AKSアルゴリズムとは、2002年8月6日に、PRIMES is in Pという論文の中に示された決定性多項式時間の素数判定アルゴリズムである。素数に関係する世界では大変話題になった。アルゴリズムの名前は、論文の著者であるインド工科大学計算機科学工学部のManindra Agrawal教授と、その学生であるNitin Saxena

[nisemono_san]

“ ”

[mhrs]

素數判定アルゴリズム。

[mind]

上のどの問題も抱えていない初めてのアルゴリズム。素数判定という理論上も応用上も極めて重要な問題が実際にクラスPに属する…。過去の高速アルゴリズムと比較して単純。証明も初歩的な代数学の知識だけ

[yujiorama]

AKSアルゴリズムとは、2002年8月6日に、PRIMES is in Pという論文の中に示された決定性多項式時間の素数判定アルゴリズムである。