４．p+1 method

以前、Lucas列について述べた。

Lucas列の y_n の方は、素数 p について、

y_p-1≡0 (mod p)

または、

y_p+1≡0 (mod p)

が成り立つ。
今、y_p+1≡0 (mod p) が成り立っているとしよう。
このとき、p+1 の倍数 M についても、y_M≡0 (mod p) となる。

以下は、p-1 method のときの議論と同じ要領である。

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

y_M≡0 (mod n)

となったとき、g = gcd(y_M,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 の値をダイレクトに使用しているため、
すぐ桁あふれしてしまう、という点に問題がある。
y_M を毎回１から求めるのではなく、y_M の結果を元に、y_M+k を求めるような修正が必要である。

そのための改造案はあるが、ここでは示さない。
今では、これより強力な楕円曲線法 (Elliptic Curve Method)というアルゴリズムがあり、
この p+1 method が使われることはあまりない。