ポラード・ローのアルゴリズム風アルゴリズム

ポラード・ローのアルゴリズム風アルゴリズム

ポラード・ローのアルゴリズムがインチキで無意味だと思ってる人向け。

1204を素因数分解する。

1.まず、1204と600を対応させる。

2.そうしたら、分かりやすいように今1204/600 という分数を作る。これはおよそ2。

3.そして、600を可能な限り多い手段で素因数分解して2つの素因数の積にする。

4.この素因数分解の結果の下記の右側の数に2.で求めた2をかけると、近似解が出てくる。

1と600、2と300、3と200$\cdots$
この候補から解の近似値を探す。
ないなら600を700、800$\cdots$に替えて探す。