2015/07/26

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

分野: 整数問題  レベル: マニアック

ポラードのロー法という素因数分解の高速なアルゴリズムを解説します。

素因数分解のアルゴリズム

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

アルゴリズムの手順

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

$f(x)=x^2+1\:\mathrm{mod}\: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$ のとき,あきらめる(失敗)

成功すればハッピー

ロー法が成功したときには $N$ の非自明な素因数が得られている。

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

失敗する確率は低い

$N$ が合成数のときロー法が失敗する確率は低い(と期待できる)。

(説明)
$N$ の非自明な約数で最も小さいものを $p$ とする。 $p \leq \sqrt{N}$ である。

$|x_i-y_i|$ が $p$ の倍数だが $N$ の倍数でない,という状況になれば成功。その前に $x_i=y_i$ という状況になってしまうと失敗。

ところが $x_i,y_i$ は $0$ 以上 $N$ 未満の値をそれなりにランダムに取るとみなせる(注)ので,$x_i=y_i$ となる確率は低い(その前に成功する確率が高い)。

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

高確率で短時間で終了する

$N$ が合成数のとき,$i=N^{\frac{1}{4}}$ くらいまでやればロー法は高確率で終了する(と期待できる)。

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

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

(説明)
$x_i$ を $p$ で割った余りを $x’_i$ とおく。

$x’_i$ は $0$ 以上 $p$ 未満の値をそれなりにランダムに取る(ここが厳密でない)とみなせるので,先述の定理より $k\geq\sqrt{p}$ とすれば高確率で $x’_1,x’_2,\cdots, x’_k$ の中に等しいものが存在する。その中で添字の大きい方の番号が最小なペアを $x’_A,x’_{A+B}$ とおく。

ロー法の様子

数列の定め方より,正の整数 $s,t$ が「いずれもが $A$ より大きくて二つの差が $B$ の倍数」なら $x’_s=x’_t$ となる(→注)。

そこで,$A$ 以上 $A+B$ 未満の整数で $B$ の倍数であるもの(ただ一つある)を $C$ とすると,$C$ と $2C$ は「いずれもが $A$ より大きくて二つの差が $B$ の倍数」なので $x’_{2C}=x’_C$ となる。よって,$|x_{2C}-x_{C}|$ は $p$ の倍数。

つまり遅くとも $i=C$ でロー法が終了することが分かる。
$C\leq A+B\leq k\simeq \sqrt{p}\leq N^{\frac{1}{4}}$ である。

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

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

$\rho$ でなくても,数字の $6,9,\sigma$(小文字のシグマ)などでもよいですね。

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

分野: 整数問題  レベル: マニアック