ポラード・ロー法 - projectpn

ポラード・ロー素因数分解法はいわゆる誕生日のパラドックス(実際にはパラドックスではないが)を用いた素因数分解法である。

入力:素因数分解する自然数n 乱数関数f(x):xは乱数の種
出力:nの約数dまたは「失敗」
動作
ステップ1

ステップ2

ステップ3
dが1ならステップ2に戻る。
dがnなら「失敗」と出力して終了。
それ以外の時はdを出力して終了

このアルゴリズムはnが素数のときは、常に失敗する。合成数の場合でも失敗することがあるが、その場合はf(x)を変えて実行する。

(解説は未完成)