翻訳と辞書 Words near each other ・ ソロノキ ・ ソロバン ・ ソロバンド ・ ソロバンドック ・ ソロパーカ ・ ソロファ・ファトゥ ・ ソロフキ ・ ソロフラ ・ ソロプチミスト ・ ソロプロジェクト ・ ソロベイ–シュトラッセン素数判定法 ・ ソロベツキー諸島 ・ ソロボダン・ミロシェビッチ ・ ソロマナ・カンテ ・ ソロムコ ・ ソロモニヤ・サブーロヴァ ・ ソロモン ・ ソロモン (ガンダムシリーズ) ・ ソロモン (ピアニスト) ・ ソロモン (ヘンデル) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

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