以前、Lucas列について述べた。
Lucas列の yn の方は、素数 p について、
yp-1≡0 (mod p)
または、
yp+1≡0 (mod p)
が成り立つ。
今、yp+1≡0 (mod p) が成り立っているとしよう。
このとき、p+1 の倍数 M についても、yM≡0 (mod p) となる。
以下は、p-1 method のときの議論と同じ要領である。
n の素因数 p が、実は、p+1 が小さい素数の積で構成されているような数である、としよう。
(必ず、という訳ではないが、あり得ない、という訳でもない)。
今、p の値は具体的にわからないから、p+1 で割り切れるような値 M を構成することはできない。
しかし、M として、充分大きな値をとっておけば、p+1 を割り切ることがあるはずである。
このような M を構成しておいて、
yM≡0 (mod n)
となったとき、g = gcd(yM,n) を計算すると、1 < g < n となり、n の素因数が見つかることがある。
これを、Hugh Williams の p+1 method と呼ぶ。
プログラムは以下のとおり。
10 ' p+1 method 20 M=1:I%=1:P=prm(I%) 30 while P<100:M=M*P^10:inc I%:P=prm(I%):wend 40 while P<1000:M=M*P^2:inc I%:P=prm(I%):wend 50 L%=len(M) 60 input "n=";N 70 P=prmdiv(N):if P>1 then print P;"*";:N=N\P:goto 70 80 ' 90 for A%=1 to 100:print:print "(a,b)=";A%;","; 100 for B%=1 to 10:print B%;:C=0:D=1 110 for I%=L%-1 to 0 step -1 120 if bit(I%,M)=0 then Nc=2*C*D-A%*C*C:Nd=D*D+B%*C*C 130 if bit(I%,M)=1 then Nc=D*D+B%*C*C:Nd=A%*D*D+2*B%*C*D 140 C=Nc@N:D=Nd@N 150 next I% 160 G=gcd(C,N):if or{G=1,G=N} then 170 else print:print G:N=N\G 170 next B% 180 next A%
この方法は、p-1 method に比べて時間がかかる、というのが難点である。
特に上のプログラムにおいて、M の値をダイレクトに使用しているため、
すぐ桁あふれしてしまう、という点に問題がある。
yM を毎回1から求めるのではなく、yM の結果を元に、yM+k を求めるような修正が必要である。
そのための改造案はあるが、ここでは示さない。
今では、これより強力な楕円曲線法 (Elliptic Curve Method)というアルゴリズムがあり、
この p+1 method が使われることはあまりない。
前 | この章の目次 | 次 |
---|