|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 素 ： [もと] 1. (n,n-suf,n-t) (1) origin 2. basis 3. foundation ・ 素因 ： [そいん] (n) basic factor ・ 素因数 ： [そいんすう] (n) prime factor ・ 因 ： [いん] 【名詞】 1. cause 2. factor ・ 因数 ： [いんすう] (n) factor (in math) ・ 因数分解 ： [いんすうぶんかい] 1. (n,vs) factorization 2. factorisation ・ 数 ： [すう, かず] 1. (n,n-suf) number 2. figure ・ 分 ： [ぶん, ふん] 1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1 ・ 分解 ： [ぶんかい] 1. (n,vs) analysis 2. disassembly ・ 解法 ： [かいほう] (n) (key to) solution ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
ポラード・ロー素因数分解法（英: Pollard's rho algorithm）は、特殊用途の素因数分解アルゴリズム。1975年、ジョン・ポラードが発明した。合成数を素因数に効率的に分解する。 ==概念== 一般に素因数分解は、対象の数 ''n'' について、その平方根以下の全ての素数について ''n'' を割ってみる。しかし、これは ''n'' が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。ポラード・ロー素因数分解法は、そのような場合に大きな素因数を確率的に探す乱択アルゴリズムである。 このアルゴリズムはフロイドの循環検出法に基づいており、また2つの数 ''x'' と ''y'' が ''p'' で割り切れるには、ランダムに 個の数を選んだとき半分以上の確率で共に割り切れるという観測結果に基づいている（誕生日のパラドックスを参照）。''p'' が素因数分解したい ''n'' の素因数であるとき、''p'' で も ''n'' も割り切れるので、 が成り立つ。 従ってこのアルゴリズムは、擬似乱数発生に ''n'' を法として使う。同じ乱数列を2回利用する。つまり、繰り返し毎に一方は順次擬似乱数列を生成し、もう一方は1つ飛びに擬似乱数列を利用する。前者を ''x''、後者を ''y'' とする。繰り返し毎に |''x'' − ''y''| と ''n'' の最大公約数(GCD)を求める。このGCDが ''n'' になった場合、このアルゴリズムは失敗して停止する。というのは、これは ''x'' = ''y'' であることを意味し、フロイドの循環検出法により、それ以降の擬似乱数列がそれまでの繰り返しになってしまうことを示しているからである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ポラード・ロー素因数分解法」の詳細全文を読む スポンサード リンク
|