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
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
多項式時間素数判定アルゴリズム
ＡＫＳアルゴリズムと 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
数独インデックス - SUDOKU Index
実行ボタンを押すと，それぞれのプログラムが実行され，約１５秒ほどで答えが戻ります 数独インデックスから解盤面へ 数独のIndexを入力 (0〜6670903752021072936959) 解盤面から数独インデックスへ 数独の盤面を入力（９×９の数字列；半角数＆改行） 概要 数独の解盤面は，大ざっぱにいうと， 約 60 垓個（6 の後ろに 0 が 21 個並ぶ）通りあることが知られています． 我々は， その解盤面一つ一つに番号付け（数独インデックス）を与えました． このページでは， 解盤面→数独インデックス，数独インデックス→解盤面の両方が， 約 10 秒程度で計算できます． 右のフォームから実行できるので， 試してみてください． 注釈： 「数独」はニコリの登録商標．一般名は Number Place です． 対象とするのは１〜９までの数を埋める通常の数独です． B. Felgenh
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
