ysd@KLab > 因数分解

p-(ひく)1法です。原理や方法を知れば名前の意味が分かるかも。発明者はいろんな因数分解アルゴリズムを見つけてるPollardです。

pが素数で、aがpの倍数ではない自然数ならば

a^p-1≡1　(mod p)

そして、その対偶をとったものが簡易素数判定に使われるフェルマーテスト。でもp-1法には関係ない。

互いに素な2つの自然数 n と a について

a^n-1≡1　(mod n)

が成り立っていなければ(上の式で合同の否定を表記できないために地の文で否定)、n は合成数。

ここからが原理本番。スタートはフェルマーの小定理の式。

Kを K=k(p-1)、つまりp-1の倍数とすると

a^K=a^k(p-1)≡1^k=1　(mod p)
∴a^K-1≡0　(mod p)

より a^K-1 が p の倍数となることが分かる。ここで何とか K つまり p-1 の倍数を上手く作れれば、GCD(a^K-1,n)=p となるかもしれない。

因数分解したい数 n の素因数の一つを p とする。仮に p-1 が小さな素因数ばかりで因数分解できると勝手に仮定すると、例えば

K = k! = k(k-1)(k-2)(k-3)…2･1

と置けば K が p-1 の倍数になる可能性は高い。この K の構成はあくまで一例なので、条件(Kがp-1の倍数になる)を満たしそう(pの値が分かっていないので確定的なことは言えない)ならどのように構成しても良い。

この K を用いて GCD(a^K-1,n) を計算する。a は2と固定しても構わないし、2と3と5と…と複数試しても良い。

p-1法