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

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

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

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

アルゴリズムの手順

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

f(x)=x2+1modNf(x)=x^2+1\bmod{N} とします。 x1x_1 を適当な数として,xk+1=f(xk)x_{k+1}=f(x_k) で数列 xkx_k を定めます。また,yk=x2ky_k=x_{2k} とします。

手順0(初期化)

i=1i=1 とする

手順1(計算)

xix_iyiy_i を計算する,xiyi|x_i-y_i|NN の最大公約数 dd を計算する

手順2(判定)

d=1d=1 のとき,ii11 増やして手順1に戻る(再挑戦)

1<d<N1 <d <N のとき,「ddNN の素因数である」と出力(成功)

d=Nd=N のとき,あきらめる(失敗)

成功すればハッピー

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

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

失敗する確率は低い

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

説明

NN の非自明な約数で最も小さいものを pp とする。pNp \leq \sqrt{N} である。

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

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

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

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

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

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

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

説明

xix_ipp で割った余りを xix'_i とおく。

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

ロー法の様子

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

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

つまり遅くとも i=Ci=C でロー法が終了することが分かる。

CA+BkpN14C\leq A+B\leq k\fallingdotseq \sqrt{p}\leq N^{\frac{1}{4}} である。

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

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

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

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