Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

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

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

因数分解したい合成数をnとします。
合成数nが n=p \times q
のように分解される時、素数pを求めたいです。 qはとりあえず合成数としておきます。

Bを自然数とし、以下の最小公倍数(Least Common Multiple)の値mを考えます。
m=lcm(1, 2, 3, ..., B)
mは最小公倍数なのですから、mはBの倍数です。
cを整数として、
 m = B c (式A)
と書けます。

p-1がB-power-smoothであると仮定します。

B-power-smoothについてはこちら B-smooth と B-power-smooth - Pebble Coding

この時、p-1はBで割り切れます。つまりp-1はBの倍数です。
dを整数として、
 p-1 = B d (式B)
と書けます。

(式A)(式B)より、mがBの倍数、p-1がBの倍数なのですから、
 p - 1 \le m
であれば、mはp-1で割り切れる(mはp-1の倍数)ことを示しています。

fを整数とし、
 m = (p-1) fとなります。

aとpが違いに素であれば、
 a^{m} = a^{ (p-1) f} = {(a^{p-1})}^f = 1^{f} = 1\mod pとなり、

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

a,mの値を変えながらgcdの値を計算していきますが、
計算量が少なくて済むようにa,mともに小さい値から試していきます。
aは通常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