まず、Fermatの小定理について述べる。
Fermatの小定理
ap-1 ≡ 1 (mod p)が成り立つ。
(p-1)乗について成り立つので、(p-1) の倍数 M についても成り立つ。
そこで、n の素因数 p が、実は、p-1 は小さい素数の積で構成されているような数である、としよう。
(必ず、という訳ではないが、あり得ない、という訳でもない)。
今 p の値は具体的にわからないから、p-1 で割り切れるような値 M を構成することはできない。
しかし、M として、充分大きな値をとっておけば、p-1 を割り切ることがあるはずである。
このような M を構成しておいて、
aM ≡ 1 (mod n)
となったとき、g = gcd(aM-1, n) を計算すると、1 < g < n となり、
n の素因数が見つかることがある。
これを、Pollard の p-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 桁の因数が見つかった。
つぼにはまったときは、なかなか強力なアルゴリズムである。
前 | この章の目次 | 次 |
---|