翻訳と辞書 Words near each other ・ ミラ・モレルセン ・ ミラ・リキヤのニコライ ・ ミラ・リキヤの聖ニコライ ・ ミラ・リャン ・ ミラ・リュン ・ ミラー ・ ミラー (ビール) ・ ミラー (フリゲート) ・ ミラー (曖昧さ回避) ・ ミラー-ラビン素数判定法 ・ ミラー–ラビン素数判定法 ・ ミラーの立体 ・ ミラーを拭く男 ・ ミラーアップ ・ ミラーガラス ・ ミラーサイクル ・ ミラーサイト ・ ミラージュ ・ ミラージュ (GOING UNDER GROUNDの曲) ・ ミラージュ (フリートウッド・マックのアルバム) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ミラー–ラビン素数判定法 ： ウィキペディア日本語版 ミラー–ラビン素数判定法 ミラー–ラビン素数判定法（）またはラビン–ミラー素数判定法（）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や Solovay-Strassen 素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンはこれを無条件の確率的アルゴリズムに修正した。 == 概念 == フェルマーや Solovay–Strassen の素数判定法と同様、ミラー–ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。 まず、有限体 $\backslash mathbb\_p$ の単位元の平方根についての補題を考える。ここで、''p'' は奇素数である。''p'' を法とした剰余（mod ''p''）において、1と-1の二乗は常に1となる。これらを 1 の「自明な」平方根と呼ぶ。''p'' は素数なので 1 の「自明でない」平方根は存在しない。これを示すため、1 mod ''p'' の非自明な平方根を ''x'' とする。このとき、以下が成り立つ: :$$ x^ \equiv 1\pmod :$$ x^ - 1 \equiv 0\pmod :$$ \left (x - 1 \right ) \left ( x + 1 \right ) \equiv 0\pmod ''p''は素数なので、これは$x-1$ または $x+1$ が ''p''で割り切れることを示す。一方、''x'' は 1 でも -1 でもないので(mod ''p'')、 $x-1$ も $x+1$ も ''p'' で割り切れない。すなわち、二乗して 1 (mod ''p''）となるのは、1 および -1 だけということになる。 さて、''n'' を奇素数としたとき、''n'' − 1 を $2^s\; \backslash cdot\; d$ と表現できる。ここで ''s'' は正整数で、''d'' は奇数である。つまり、''d'' は ''n'' − 1 を繰り返し 2 で割った結果と同じである。すると、全ての $a\backslash in\; \backslash left(\backslash mathbb/n\backslash mathbb\backslash right)^$ * について: :$$ a^ \equiv 1\pmod または、ある $0\; \backslash le\; r\; \backslash le\; s-1$ に対して :$$ a^ \equiv -1\pmod が成立する。 これらのいずれかが真となることを示すため、以下のフェルマーの小定理を利用する: :$$ a^ \equiv 1\pmod ここで、 :$$ a^ = a^ \equiv 1\pmod であるから、この平方根は上述の補題から 1 または −1 （mod ''n''）である。−1 の場合は後者の合同式が成り立つ。 1 の場合はさらに平方根を考えていくと、上述の補題から 1 または −1 （mod ''n''）となる。一度も −1 （mod ''n''）とならないまま、''r'' = 0 となったとする。 :$$ a^ = a^d \not\equiv -1\pmod この場合後者の合同式は成立せず、前者の合同式が成立する。 ミラー-ラビン素数判定法は上記の主張の対偶に基づいている。すなわち、整数 ''n'' に対し、以下が成り立つ ''a'' を見つけたとする。 :$$ a^ \not\equiv 1\pmod かつ、任意の $0\; \backslash le\; r\; \backslash le\; s-1$ に対して :$$ a^ \not\equiv -1\pmod すると、''n'' は合成数であり、''a'' は ''n'' の合成性の証拠（証人）である。証拠とならない ''a'' を「強い嘘つき; strong liar」と呼び、''n'' を底 ''a'' についての「強擬素数; strong pseudoprime」と呼ぶ。「強い嘘つき」とは、''n'' が合成数であるのに合同式が成立することによって素数であると嘘をつくことから来ている。 奇数の合成数には、多くの証拠（証人）''a'' がある。しかし、そのような ''a'' を生成する単純な方法は知られていない。ミラー-ラビン素数判定法では、$a\; \backslash in\; \backslash left(\backslash mathbb/n\backslash mathbb\backslash right)$ であるような数をランダムに選択し、それが ''n'' の合成性の証拠（証人）となりうるかを調べる。''n'' が合成数なら、ほとんどの ''a'' は証拠となるので、高い確率で ''n'' が合成数であることを検出できる。しかし、不運にも ''n'' に対する「強い嘘つき」となる ''a'' を選んでしまう可能性も若干ある。この確率を減らすには、いくつかの独立に選んだ ''a'' で判定を繰り返す。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ミラー–ラビン素数判定法」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.