１．はじめに

或る整数Ｎの約数を見つけたい時、一番原始的なのは√N以下の素数で順番にＮを割って調べる方法です。
でもこの方法だとN=10^10の時に、√N=10^5で10^5以下の素数の数は約９６００個だから
最悪９６００回Ｎを割らないと約数が見つからないことになります。

そこでフェルマ(1601-1665)は次の様に考えました。
N=x^2-y^2　とNを平方数の差で表せたとします。すると
N=(x-y)*(x+y)　と分解されます。すなわちa=x-y,b=x+yが約数になる訳です。


それでは実際にはどのように行うかを説明します。

x0=√N+1 としてy0=x0^2-Nを求めて平方数かどうかチェックします。

一般的には

x(i+1)=x(i)+1
y(i+1)=x(i+1)^2-N

となって  y(i+1)求めて平方数かどうかチェックします。
       
UBASICで実際にプログラムを作りました、次の様になります。

　　プログラム名：fermat.ub

   10      input "N=";N
   20      x0=isqrt(N)+1
   30      x=x0
   40      while x <= N/2
   50          if x@10000 = 0 then print "x=",x
   60          y=x^2-N
   70          sy=isqrt(y)
   80          if sy^2 <> y then goto 100
   90          print  "factor is=",x-sy,x+sy:goto 1000
  100          x=x+1
  200      wend 
 1000       end



3.計算例

N=2601542189　とすると

i      x(i)     y(i)
0     51006     69847
1     51007    171860
2     51008    273875
3     51009    375892
4     51010    477911
5     51011    579932
6     51012    681955
7     51013    783980
8     51014    886007
9     51015    988036

988036=994^2 となるので　N=(51015-994)*(51015+994)=50021*52009 と分解できました。
因みに50021、52009　は素数です。
小さい素数で割る方法だと、兀(50021)=5134 だから5134回試行する所を、
この例では、N=a*b とした時a≒bであるので僅か１０回の試行で見つかりました。
何故なら、a≒b の場合に一番試行回数を少なく出来るからです。
従って、a≫b の場合はフェルマの方法は、試行回数が多くなり不向きとなるでしょう。

次に試行回数が多い場合を扱ってみましょう。
N=2^32+1=4294967297

       i      x(i)          y(i)
       1     65537         131072
       2     65538         262147
       3     65539         393224
       4     65540         524303
       5     65541         655384
       6     65542         786467
       7     65543         917552
       8     65544        1048639
       9     65545        1179728
       .
       .
 3284981   3350517 11221669199992
 3284982   3350518 11221675901027
 3284983   3350519 11221682602064
 3284984   3350520 11221689303103
 3284985   3350521 11221696004144
 3284986   3350522 11221702705187
 3284987   3350523 11221709406232
 3284988   3350524 11221716107279
 3284989   3350525 11221722808328
 3284990   3350526 11221729509379
 3284991   3350527 11221736210432
 3284992   3350528 11221742911487
 3284993   3350529 11221749612544

11221749612544=3349888^2 なので N=(3350529-3349888)*(3350529+3349888)=641*6700417
と分解されました。
試行回数3284993回でやっと分解された訳で、a≫b の場合はやはり厳しいですね。


上に示したプログラムで因数分解をして遊びましょう！

UBASIC　がインストールされている事を前提にします。

１．fermat.ub　を UBV32.exe が有るフォルダにコピーする。

２．UBV32.exe　を起動する。

３．load "fermat" と入力する。（fermat.ub　をメモリ上にロードします）

４．run と入力する(メモリ上のプログラムを実行します）

５．N=?　が表示されたら因数分解したい数字を入力して下さい。

６．プログラムを途中で止める場合は、CNTL+C と入力して下さい。
　　それでも駄目な場合は、CNTL+BREAKキー を入力して下さい。
　　それでも駄目な場合は、CNTL+ALT+DELETE でタスクマネージャからUBASICを終了させて下さい。

７．プログラム正常終了後に、UBASIC　を終了させるには、system と入力して下さい。


８．注意事項

　　・因数分解する数字は１０桁位が処理時間からして適当と思われます。
　　　勿論、N=a*bで,a≒b の場合は桁数が大きくても試行回数は少なくて済みます。


　　・因数分解する数字が素数の場合は、当然のことながら試行回数は多くなります。