１．はじめに

前回のモンテカルロ法を考案したＰｏｌｌａｒｄが、今回も登場します。
彼は１９７４年に、Ｐ−１法という素因数分解の方法を考えました。
まず、素因数分解したい数をNとして、a,Mを適当に与えると次の式でNが分解されてしまうのです！
すなわち、GCD(a^M-1,N)を評価する事によりNの素因数Pを見つける事ができます。
この考え方は非常にシンプルでフェルマーの小定理を応用しているだけです。

フェルマーの小定理

　　Pは素数、(a,P)=1　とした時

　　a^(P-1)≡1 mod P

原理

　　N:　素因数分解したい整数,N=P*Q　とする　　
　　P:　Nの素因数
　　M:　P-1の倍数
　　a:　Pの約数でない整数

   フェルマーの小定理によって、a^M≡1 mod P　となります。
   従って、a^M-1　はPの倍数になる事がわかります。　　
   a^M-1≡0 mod P, N≡0 mod P, だから結局　GCD(a^M-1,N)≡0 mod P　となります。

   要するに大きな値のMをなんらかの方法で作って、GCD(a^M-1,N)を評価する事によりNの素因数Pを
   見つける事ができると言うことになります。　　


まず、例から始めましょう。
例１．

   N=2831071=61*46411

   2^2          mod P =3        GCD(2^2-1,        2831071)=1
   2^(2*3)      mod P =63       GCD(2^(2*3)-1,    2831071)=1
   2^(2*3*4)    mod P =2621860  GCD(2^(2*3*4)-1,  2831071)=1
   2^(2*3*4*5)  mod P =2539613  GCD(2^(2*3*4*5)-1,2831071)=61

   61-1=2^2*3*5

   61の素因数が2,3,5であるので、GCD(2^M-1,2831071)でM=2*3*4*5の様に、Mが素因数の2,3,5の積に
   なった所で2831071の素因数61が予想通り発見されました。

   この例から判ることは、2831071の素因数である61が61-1=2^2*3*5と小さな素数の積に表せる為に
   試行回数が４回で分解出来たと言う事です。
   逆に言えばNの素因数PがP-1=2*Q(Qは大きい素数)のように分解されるような場合は、試行回数は
   最悪のケースになることが予想されます。
   次の例では、Nの大きさの割合に比べると試行回数が多くなるケースです。


例２．

  N=10669=47*227
  47-1=2*23
  227-1=2*113
  GCD(2^(2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23)-1,10669)=47


  一般に、GCD(a^M-1,N)　においてMは、M=p1^a1*p2^a2*p3^a3.....の様に小さな素数のべき乗の積に
  表されので、簡便のためM=2*3*4*5*6.....の様に小さい数の階乗で構成する様にします。


    
UBASICで実際にプログラムを作りました、次の様になります。

　　プログラム名：P1.ub

    Ｎ　　　　　：素因数分解したい数
　　ｓｅｅｄ　　:　ａ＾Ｍにおけるａ（通常は２、３等）
    Ｂ　　　　　:　ａ＾ＭにおけるＭ（通常は１０００００迄）




   10   input "N=";N:input "seed=";seed:input "B=";B
   20   a=seed
   30   G=1:cnt=0
   40   M=1
   50   while G<=1
   60       M=M+1
   65       if M >= B then goto 200
   70       if M@10000 = 0 then print "M=";M
   80       a=modpow(a,M,N)
   90       G=gcd(a-1,N)
  120   wend
  130   if G > 1 and G < N then print "factor is ";G," M=";M
  140   :else print "try new seed""  
  150   if modpow(2,G-1,G) <> 1 then print G," is not prime"
  160   :else print G,"  may be prime"
  200   end






3.計算例



N=2^512+1
 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 
factor is  2424833 	 M= 37 
最終的には、N=2424833 * 7455602825647884208337395736200454918783366342657 * P99 
2424833-1=2^16*37



N=2^1024+1
 = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217 
factor is  6487031809 	 M= 41 
最終的には、N=45592577 * 6487031809 * 4659775785220018543264560743076778192897 * P252
6487031809-1=(2)^14*(3)^2*(29)*(37)*(41)
45592577-1=(2)^12*(11131)
6487031809-1の素因数の方が45592577-1の素因数より小さいので、6487031809が先に分解されている。
この例の様に試行回数は素因数Ｐの大きさではなく、素因数Ｐ−１の素因数の大きさに依存する事が
わかります。



N=2^67-1= 147573952589676412927 
factor is  193707721 	 M= 2677 
N=193707721*761838257287
193707721-1=(2)^3*(3)^3*(5)*(67)*(2677)




N=2^128+1=340282366920938463463374607431768211457 
この場合は、他の方法でN=59649589127497217 * 5704689200685129054721と分解されるが 
59649589127497217-1=(2)^9*(116503103764643)
5704689200685129054721-1=(2)^9*(3)^5*(5)*(733803839347)*(12497)
とどちらの素因数−１も大きな素数が含まれているので、Ｐ−１法はまったく無力な例です。