翻訳と辞書 Words near each other ・ ポラロン ・ ポラロン雑種DNAモデル ・ ポラン ・ ポランスキ ・ ポランスキー ・ ポランスキーの パイレーツ ・ ポランスキーの 欲望の館 ・ ポランニ ・ ポランニー ・ ポラード・ミャオ ・ ポラード・ロー素因数分解法 ・ ポラード文字 ・ ポラーニ ・ ポラーニ・カーロイ ・ ポラーニ・ミハーイ ・ ポラーノ ・ ポラーノの広場 ・ ポラーブ語 ・ ポラーヴェノ ・ ポリ Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ポラード・ロー素因数分解法 ： ウィキペディア日本語版 ポラード・ロー素因数分解法[ぽらーどろーそいんすうぶんかいほう] ポラード・ロー素因数分解法（英: Pollard's rho algorithm）は、特殊用途の素因数分解アルゴリズム。1975年、ジョン・ポラードが発明した。合成数を素因数に効率的に分解する。 ==概念== 一般に素因数分解は、対象の数 ''n'' について、その平方根以下の全ての素数について ''n'' を割ってみる。しかし、これは ''n'' が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。ポラード・ロー素因数分解法は、そのような場合に大きな素因数を確率的に探す乱択アルゴリズムである。 このアルゴリズムはフロイドの循環検出法に基づいており、また2つの数 ''x'' と ''y'' が ''p'' で割り切れるには、ランダムに $1.177\backslash sqrt$ 個の数を選んだとき半分以上の確率で共に割り切れるという観測結果に基づいている（誕生日のパラドックスを参照）。''p'' が素因数分解したい ''n'' の素因数であるとき、''p'' で $\backslash left|x-y\backslash right|$ も ''n'' も割り切れるので、 が成り立つ。 従ってこのアルゴリズムは、擬似乱数発生に ''n'' を法として使う。同じ乱数列を2回利用する。つまり、繰り返し毎に一方は順次擬似乱数列を生成し、もう一方は1つ飛びに擬似乱数列を利用する。前者を ''x''、後者を ''y'' とする。繰り返し毎に |''x'' − ''y''| と ''n'' の最大公約数(GCD)を求める。このGCDが ''n'' になった場合、このアルゴリズムは失敗して停止する。というのは、これは ''x'' = ''y'' であることを意味し、フロイドの循環検出法により、それ以降の擬似乱数列がそれまでの繰り返しになってしまうことを示しているからである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ポラード・ロー素因数分解法」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.