ポラード・ロー素因数分解法(英: Pollard's rho algorithm)は、特殊用途の素因数分解アルゴリズム。1975年、ジョン・ポラード(英語: John Pollard)が発明した。合成数を素因数に効率的に分解する。 概念[編集] 一般に素因数分解は、対象の数 n について、その平方根以下の全ての素数について n を割ってみる。しかし、これは n が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。ポラード・ロー素因数分解法は、そのような場合に大きな素因数を確率的に探す乱択アルゴリズムである。 このアルゴリズムはフロイドの循環検出法に基づいており、また2つの数 x と y が p で割り切れるには、ランダムに 個の数を選んだとき半分以上の確率で共に割り切れるという観測結果に基づいている(誕生日のパラドックスを参照)。p が素因数分解したい n の素因数であると