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
最速の素数判定アルゴリズム
1 ： 刺身定食：2001/06/25(月) 17:22 最速のアルゴリズムはRabinの定理を使ったものと聞き、 文献を読んでみたのですが、サッパリわかりません。 日本で完璧に理解している方、たまたまこのスレ 見ていたら、ついでに教えてください。 マジです。 2 ：デフォルトの名無しさん：2001/06/25(月) 18:27 >>1 理解できないのならあきらめるしかないでしょう。 他人をたよるのはよくありません。 3 ：デフォルトの名無しさん：2001/06/25(月) 19:22 >>1 その「さっぱり」って言葉がやるきねぇなぁと他人に感じさせるので、 そういう聞き方では知識ナルシスト以外教えてくれないと思われ。 4 ：デフォルトの名無しさん：2001/06/25(月) 19:26 エラストテネスの篩で我慢しろ。 5 ：デフォルトの名無しさん：2001/06/25(月) 20:15
フェルマーテストによる素数判定
最近の主な更新 2005-11-25 - 細かな修正 2005-11-22 - 第二版 2004-09-12 - 初版 概要 本稿では，確率的素数判定法の一つであるフェルマーテストについて述べる． 1章ではフェルマーテストの理論的基礎であるフェルマーの小定理を導く．2章 では，フェルマーテストの Python による実装を与える．3章では，フェルマー テストによる素数判定が誤る原因となる，擬素数の存在について述べる． 1 フェルマーの小定理 フェルマーテストの準備として，以下ではフェルマーの小定理とよばれる定理 を導く．まず，次の補題が成り立つ． 補題 1.1 素数 p と 自然数 r （0 < r < p）に対し， pCr = p! / (r!(p-r)!) ≡ 0 (mod p) が成り立つ． 証明 p! は p で割りきれる．一方，r!(p-r)! は p よりも小さい自然 数の，複
多項式時間素数判定アルゴリズム
ＡＫＳアルゴリズムと PRIMES is in Pに関する解説のページです 以下の説明は、元論文を参照しながらお読みください。 元論分のサイト：Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P, the original version of the paper. アルゴリズムの基本となるアイデア アルゴリズムの概要 AKS アルゴリズム 使用する用語と記号 アルゴリズムの動作概要 アルゴリズムの正当性の証明概要 アルゴリズムの正当性の証明の蛇足説明 アルゴリズムの正当性の証明詳細のための準備 PRIMES is in P セクション３の解説 Lemma 3.1. Lemma 3.1.(fact 1) Lemma 3.1.(fact 2) Lemma 3.1.(fact 3) Lemma 3.1.(fact 4
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
