翻訳と辞書 Words near each other ・ AKIRA (ダンサー) ・ AKIRA (ファッションモデル) ・ AKIRA (プロレスラー) ・ AKIRA (女性アーティスト) ・ AKIRA (漫画) ・ AKI猪瀬 ・ AKMテクノロジ ・ AKN鉄道 ・ AKR共栄会 ・ AKS素数判定 ・ AKS素数判定法 ・ AKTこんやのニュース ・ AKTみんなのニュース ・ AKTザ・ヒューマン ・ AKTザ・ヒューマンあきた ・ AKTスーパータイム ・ AKTスーパータイムあきた ・ AKTスーパーニュース ・ AKTスーパーニュース FNN ・ AKTスーパーニュースあきた Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク AKS素数判定法 ： ミニ英和和英辞書 AKS素数判定法[-そすうはんていほう] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 素 ： [もと] 　 1. (n,n-suf,n-t) (1) origin　2. basis　3. foundation ・ 素数 ： [そすう] 　(n) prime numbers ・ 数 ： [すう, かず] 　 1. (n,n-suf) number　2. figure　 ・ 判 ： [ばん] 　(n,n-suf) size (of paper or books) ・ 判定 ： [はんてい] 　 1. (n,vs) judgement　2. judgment　3. decision　4. award　5. verdict　 ・ 定法 ： [じょうほう] 　【名詞】 1. established rule　2. usual method ・ 法 ： [ほう] 　 1. (n,n-suf) Act (law: the X Act)　 AKS素数判定法 ： ウィキペディア日本語版 AKS素数判定法[-そすうはんていほう] AKS素数判定法（-そすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 $n$ が素数であるかどうかを判定するのにかかる時間が$\backslash log(n)$ の多項式を上界とすることをいう。$n$ の多項式ではないことに注意する必要がある。 AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（Nitin Saxena）の3人の名前から付けられた。 この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。 素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解した方がよい）。 == 発想 == AKS素数判定法は、ある意味ではフェルマーテストの改良と見ることができる。 フェルマーの小定理の対偶である次のような命題を考える。 : $a$, $n$ が互いに素な自然数であるとする。 ::$a^n\; \backslash \; \backslash not\backslash equiv\backslash \; a\; \backslash pmod$ : であるとき、$n$ は合成数である。 フェルマーテストはこの十分条件によって確率的素数判定を行うものであったが、上は必要条件ではないので、合成数であるにもかかわらずそれを検出できない場合があった。特に、カーマイケル数と呼ばれる合成数が無限個存在し、これらはいかなる $a$ を用いても合成数であることを検出できない。 そこで、この条件を次のように改良する。 :$a$, $n$ が互いに素な自然数であるとする。 :: $(X+a)^n\; \backslash \; \backslash not\backslash equiv\backslash \; X^n+a\; \backslash pmod$ :のとき、かつそのときに限り、(iff:if and only if) $n$ は合成数である。 このことは、二項定理により各次数の係数を評価すれば容易に証明できる。 上の式は、$X$ が恒等的に 0 だと思えばフェルマーの小定理の対偶そのものである。つまり、上の条件による判定はフェルマーテストをより厳密にしたものといえる。 厳密にしたことによりフェルマーテストとは異なり必要十分条件を与えている。したがって上の合同式を真面目に評価してやれば素数性を判定する決定性アルゴリズムができるが、これは時間がかかりすぎる。つまり、最悪の場合 $n$ 個の係数を評価しなければならないので、これは $n$ のビット数に対して指数関数時間である。 そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい $r$ をとって $X^r-1$ を法として評価する。すると、$X^r-1$ による剰余は高々 $r-1$ 次だから、評価する係数の数を減らすことができる。 :$(X+a)^n\; \backslash \; \backslash not\backslash equiv\backslash \; X^n+a\; \backslash pmod$ しかし、これは「大雑把な評価」である。評価を楽にした分、その精度も落ちている。このままでは、合成数なのに誤って素数であると判定してしまう恐れがある。そこで、パラメータ $a$ を動かして、たくさんの $a$ に対して上の合同式を評価することで埋め合わせにする。 この発想が、AKSアルゴリズムの肝である。つまり、十分にたくさんの $a$ について上の合同式を確かめれば、$X^r-1$ を法としたままでも素数性を厳密に判定することができる（これは自明ではないが、証明できる）。そして、$a$ を動かす範囲や適切な $r$ の値は $n$ に対してそれほど大きくならないので、この方法は最初の合同式を真面目に評価するより速く、多項式時間で動作する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「AKS素数判定法」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.