素因数分解の高速なアルゴリズム（ロー法）

• 素因数分解の難しさと素数判定でも述べたとおり，大きな数の素因数分解は非常に難しいです。難しいながらもできるだけ速い方法を探したいです。
• ロー法（$\rho$ -アルゴリズム）は高確率で短い計算時間で正しい答えを返しますが，失敗することもあります。実験的にはうまくいっていますが，理論的な保証はないヒューリスティックスです。

ロー法は $N$ が合成数のとき，$N$ の非自明な（$1$ でも $N$ でもない）約数を高確率で求める方法です（これを繰り返し用いることで高確率で $N$ を素因数分解できます）。

$f(x)=x^2+1\bmod{N}$ とします。 $x_1$ を適当な数として，$x_{k+1}=f(x_k)$ で数列 $x_k$ を定めます。また，$y_k=x_{2k}$ とします。

手順0（初期化）

$i=1$ とする

手順1（計算）

$x_i$ と $y_i$ を計算する，$|x_i-y_i|$ と $N$ の最大公約数 $d$ を計算する

手順2（判定）

$d=1$ のとき，$i$ を $1$ 増やして手順1に戻る（再挑戦）

$1 <d <N$ のとき，「$d$ が $N$ の非自明な約数である」と出力（成功）

$d=N$ のとき，あきらめる（失敗）

理由：ロー法が成功したとき，$|x_i-y_i|$ と $N$ の最大公約数が $d$ です。つまり $d$ は $N$ の非自明な約数です。

注：ここが怪しいです。厳密な解析は未解決問題です。

この主張の説明はだいぶ難しいですが面白いです。

異なる $p$ 種類の品物から重複を許してランダムに $\sqrt{p}$ 個（くらい）取るとき，二個以上取る品物が高確率で存在する。という定理を使います。この定理の詳細は省略しますが，誕生日のパラドックスを読めば雰囲気は分かると思います。

注：この循環する様子を図にするとギリシャ文字の $\rho$ （ロー）っぽいのでロー法，$\rho$ -アルゴリズムと呼ばれています。

なお，手順1はユークリッドの互除法を使うことで $\log N$ 回くらいの割り算でできます。よって全体の計算量は $N^{\frac{1}{4}}\log N$ くらいだと期待できます。素朴な方法（試し割り）の計算時間（だいたい $\sqrt{N}$）よりも高速です。

Tag:素数にまつわる覚えておくべき性質まとめ