素数判定・素因数分解プログラム
素数判定プログラム 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
桁未満の素因数の検出に適するかと思われます。
フェルマー数のF8まで素因数分解できます。試してみて下さい。
また，ブレント（Brent）が，ρ法を高速化するために変形アルゴリズムを作成しています。そのブレントのアルゴリズムに，さらに独自の改良を加えてみ
ました。平均すると僅かですが1割近く高速になります。
ポラードのρ素因数分解法は，次の上下に並んだ添字の項の差を用います。下の行が空白の場合は，用いません。添字の差は，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