ポラードのp-1因数分解法

大きな合成数を素因数分解(factorization in prime numbers)するアルゴリズムの一つにポラードのp-1法があります。
ポラードの $\rho$ (ロー)法とは別モノなので混同しないようにしましょう。

因数分解したい合成数をnとします。
$n=p \times q$ の時、素数pを求めたいです。qはとりあえず合成数としておきます。
ある整数mがp-1の倍数であると仮定します(mの選び方はあとで考えます) 。
kを1以上の整数とすると、
$m = (p-1) k$
aとpが違いに素であれば(aの選び方はあとで考えます)、フェルマーの小定理を使うと、
$a^{m} = a^{ (p-1) k} = {(a^{p-1})}^k = 1^{k} = 1\mod p$ となり、

$(a^{m}\mod p) - 1 = h$ はpで割り切れます。
一方、nもpで割り切れますので、hとnの最大公約数(greatest common divider)
$gcd(h, n) = g$ はpで割り切れます。
gが1より大きくnより小さい場合は、gはnの因数であることが分かります。
gが1やnになった場合はmの選び方が悪いので別の値を使って再チャレンジします。
これを繰り返せば、素因数分解を完了させることができます。

mはどうやって選べばよいでしょうか。
p-1の倍数になればよいので、ある整数cとして、以下の最小公倍数(least common multiple)を考えます。
m = lcm(2, 3, 4, 5, ..., c)
このように素因数をできるだけ多く含むようにしておけば、p-1の倍数になりやすいと言えるでしょう。
mがp-1の倍数になりにくくするには、
p-1がB-power-smooth(B-smooth と B-power-smooth - Pebble Coding)である時のBの値が大きければよいです。
つまり、p-1が大きな素数因数を含めばよいということです。

a,mの値を変えながらgcdの値を計算していきますが、
計算量が少なくて済むようにa,mともに小さい値から試していきます。
aはpと違いに素であれば良いので、通常2を使い、Bを少しづつ大きくしていくようです。
Bを大きくするとmの値が大きくなっていきます。

参考:

http://www.maroon.dti.ne.jp/fermat/factor3.html

http://www.math.mcgill.ca/darmon/courses/05-06/usra/charest.pdf