3.p-1 method


まず、Fermatの小定理について述べる。

Fermatの小定理

任意の素数 p について、p と互いに素な a について、
ap-1 ≡ 1 (mod p)
が成り立つ。

(p-1)乗について成り立つので、(p-1) の倍数 M についても成り立つ。


そこで、n の素因数 p が、実は、p-1 は小さい素数の積で構成されているような数である、としよう。
(必ず、という訳ではないが、あり得ない、という訳でもない)。
今 p の値は具体的にわからないから、p-1 で割り切れるような値 M を構成することはできない。
しかし、M として、充分大きな値をとっておけば、p-1 を割り切ることがあるはずである。
このような M を構成しておいて、

M ≡ 1 (mod n)

となったとき、g = gcd(aM-1, n) を計算すると、1 < g < n となり、
n の素因数が見つかることがある。
これを、Pollardp-1 method と呼ぶ。


このアルゴリズムは、いかにして M の値を設定するかがポイントである。
例えば、M = k! (k=1, 2, ...) という方法があるが、
この場合、k が大きくなるに従って、小さい素因数が極端に増えていく。
大きい素数を単発的に取り込んでいきたい。

今回、以下の方針をとった。

プログラムは以下のとおり。

 10   ' p-1 method
 20   X=3:I%=0
 30   input "n=";N
 40   P=prmdiv(N):if P>1 then print P;"*";:N=N\P:goto 40
 50   '
 60   while P<1000
 70     inc I%:P=prm(I%):X=modpow(X,P^10,N)
 80     G=gcd(X-1,N):if G>1 then print:print G,N\G:N=N\G:goto 80
 90   wend
100   '
110   while P<130000
120     inc I%:P=prm(I%):X=modpow(X,P^2,N)
130     G=gcd(X-1,N):if G>1 then print:print G,N\G:N=N\G:goto 130
140   wend
150   '
160   P=nxtprm(P):X=modpow(X,P,N)
170   G=gcd(X-1,N):if G>1 then print:print G,N\G:N=N\G:goto 170
180   goto 160

実行して、1061 - 1 を代入して見よう。
一瞬にして、1090826214073716053 という 19 桁の因数が見つかった。
つぼにはまったときは、なかなか強力なアルゴリズムである。


この章の目次

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典