素数判定・素因数分解プログラム


素数判定プログラム  prime.bas
「(仮称)十進BASIC」上で素数判定をするプログラムで,試行除算とミラー・ラビン素数判定法を用いています。素数でない数 を素数と誤判定する確率は1回の判定に対して2-200以 下に設定しています。同じ素数に対してn回判定を繰り返せば,誤判定する確率は2-200n以 下になりますから,素数であるかどうかをほぼ確実に判定できます。最新の「(仮称)十進BASIC」をダウンロードしてからご利用下さい。
また,プログラムを少し変形して,試行除算で素数の一覧表を作りました。他のサイト 「www.ysr.net.it-chiba.ac.jp/yashiro/sosu/」の一覧表と一致することを,「暗GO」にあるファイルのハッシュ 値を得る機能で確認しました。
素因数分解プログラム  factor.bas
上記の素数判定プログラムに,ポラードのρ素因数分解法(Pollard's rho algorithm)を 加えて,素因数分解が出来るようにしたものです。
ρ素因数分解法は,小さい素因数を高速に見つけますが,大きな素因数を見つけるのには向きません。フェルマー数のF8までは素因数分解できましたが,15桁未満の素因数の検出に適するかと思われます。
また,ブレント(Brent)が,ρ法を高速化するために変形アルゴリズムを作成しています。そのブレントのアルゴリズムに,さらに独自の改良を加えてみました。平均すると数%だけ高速になるようですが,個々では逆に遅くなる場合もあります。

ポラードのρ素因数分解法は,次の上下に並んだ添字の項の差を用います。下の行が空白の場合は,用いません。添字の差は,1,2,3,……と 連続します。

ポラードの元のアルゴリズムでは,一度計算した項を記憶すること は記 憶容量の関係で不可能なので,上の列と下の列を添字に持つ乱数列を同時に2本生成し ま す。
1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
   1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25

ブレントによる変形アルゴリズム
は,次の上下に並んだ添字の項の差を利用します。この場合,既に生成した項を1項だけ記憶することにより,乱数列 を1本だけしか生成しないで済みます。
1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
   1     2        4  4              8  8  8  8                         16 16 16 16 16 16 16 16                                                 32 32

ブレントの方法に改良を加えたアルゴリズムは,次の上下に並んだ添字の項の差を利用します。既に生成した項を何項か記憶することにより,若干の高速化を図ったもので
4項 だけ記憶する場合は
1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
            4  4  4  4     5     6     7     8       10 10       12 12       14 14       16 16             20 20 20 20             24 24 24 24
8項だけ記憶する場合は
1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
                        8  8  8  8  8  8  8  8     9    10    11    12    13    14    15    16       18 18       20 20       22 22       24 24

なお,ブレントの変形アルゴリズムをさらに改良した,十進BASICのプログラムは,次のものです。

!ρ法(変形版)
EXTERNAL FUNCTION rho(p,keisuu)
OPTION ARITHMETIC RATIONAL
DEF f(x,p)=MOD(x^2+keisuu,p)
LET bunnkatu=8
OPTION BASE 0
DIM x(bunnkatu-1)
LET y=17555985004

LET r=64
FOR j=0 TO bunnkatu-1
   FOR i=1 TO r
      LET y=f(y,p)
   NEXT I
   LET x(j)=y
NEXT J

LET j=0
LET z=1
LET k=0
DO
   DO
      LET y=f(y,p)
      LET k=k+1
   LOOP UNTIL k=r   
   DO
      LET ys=y
      LET m=MIN(1024,k)
      FOR i=1 TO m
         LET y=f(y,p)
         LET z=MOD(z*(y-x(j)),p)
      NEXT I
      LET d=gcd(p,z)
      IF d>1 THEN GOTO 100
      LET k=k-m
   LOOP UNTIL k=0
   LET x(j)=y
   LET j=j+1
   IF j=bunnkatu THEN
      LET r=r*2
      LET j=0
   END if
LOOP
100
    IF d=p THEN
       DO
          LET ys=f(ys,p)
          LET d=gcd(p,ABS(ys-x(j)))
       LOOP UNTIL d>1
    END IF
    LET rho=d
 END FUNCTION

最初のページ に戻る