|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 素 ： [もと] 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)
ソロベイ–シュトラッセン素数判定法は、とによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではやミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。 ==概要== レオンハルト・オイラーは任意の素数''p''と整数''a''に対して、 : (は)であることを証明した〔オイラーの規準〕。はルジャンドル指標を一般の奇数''n''に対するに一般化したものである。ヤコビ指標は平方剰余の相互法則のヤコビによる一般化を用いればO((log ''n'')²)時間で計算できる。 奇数''n''が与えられたとき、合同式 : が''n''と互いに素な様々な底''a''に対して成立するかどうかを考えることができる。''n''が素数なら、この合同式はすべての''a''に対して真である。そのため、ランダムに''a''を取ってこの合同式をチェックすれば、成り立たない''a''が存在した時に''n''が素数でないことが言える(ただし素因数分解は分からない)。この場合の底''a''を''n''のEuler witnessと呼ぶ。この''a''は''n''が合成数であることの証拠である。もし''n''が合成数で上の合同式が成立するならば、そのときの底''a''を''n''のEuler liarと呼ぶ。 任意の奇数の合成数''n''に対して、全ての底のうち少なくとも半分の底 : がEuler witnessである〔PlanetMath 〕。これは、証拠の数がずっと少なくなり得るフェルマーテストとは対照的である。そのため、フェルマーテストにおけるカーマイケル数の存在とは対照的に、証拠がたくさん存在しないような(奇数の)合成数''n''は存在しない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ソロベイ–シュトラッセン素数判定法」の詳細全文を読む スポンサード リンク
|