Appendix 5. 素数表(各桁・ビット数の最大/最小の素数)
(2009/01/18)
[English]
概要
n 桁の素数を生成したい場合、もっとも primitive な方法は、
まず、ランダムに n 桁の奇数を生成して素数判定を行い、
だめな場合は、2を足してまた素数判定、
という手順を繰り返す方法である。
ランダムに数を選ぶと、ほとんどの場合、合成数となるので(かつ、小さい約数を持つ場合が多いので)、
いきなり厳密な素数判定を行うのではなく、
まず小さい数(3, 5, 7)で割り切れるかどうかをチェックし、
次に、フェルマーテストでフィルターをかける。
これでほとんどの合成数は、ふるい落とされるので、
残った数に対して、もう少し厳密な素数判定を行う。
この方法により、
- n ビットの素数(2nに近い素数)
- 10nに近い素数
- n!, #Pn (n番目までの素数の積) に近い素数, #Compn (n番目までの合成数の積) に近い素数
を探してみる。
探査の個数は、それぞれの n について、
- 小さい n については、ベースとなる値に近い小さい方の10個、及び、大きい方の10個
- 大きい n については、ベースとなる値の前後1個
(∵ 計算時間がかかるため。10個探すための計算量は、最初の1個を見つける場合の約10倍。
また、n が大きくなるにつれて素数判定の時間自体が長くなる。)
- ベースとなる値からの差異が特に小さい数(±1, ±3, ±5, ±7, ±9)
とする。
素数判定は、Solovey-Strassen test で、base が 2, 3, 5, 7, 11, 13, 17, 19 の場合をチェック。
(よって、正確には素数ではなく probable prime だが、
この判定で素数と判定され、実際は合成数、
ということは、極めて稀。もし見つかればニュースになる。)
正確には、いずれ、APRT-CLE、ECPP等でまじめにチェックする必要がある。
素数表
[1] n ビットの素数
各ビット長で最初と最後の素数10個 (ビット長 n=2, ... , 2600 : Jan. 18, 2009)
各ビット長で最小と最大の素数 (ビット長 n=2, ... , 4320 : Dec. 21, 2008)
2n±1, 3, 5, 7, 9 の形の素数 (n=1, ... , 4320 : Dec. 01, 2008)
|
-
n ビットの数 N は、2n-1 ≤ N ≤ 2n-1 の範囲内にある。
この範囲内の素数を、小さい方(2n-1に近い方)、及び、
大きい方(2n-1)から求める。
これは、2n の前後の素数、とも読み替えることができる。
これらの値は、公開鍵暗号等で、鍵生成を行う場合に有用となる。
- 表の見方
|
[2] 10nに近い素数
10n の前後の素数10個ずつ
(n=1, ... , 500 : Dec. 01, 2008)
10n の前後の素数
(n=1, ... , 1300 : Dec. 11, 2008)
10n±3, 9, 10n+1, 7 の形の素数
(n=1, ... , 1300 : Dec. 01, 2008)
|
-
10n の前後の素数を求める。
この結果は、各桁数の最小・最大の素数とも読み替えることができる。
また、10n の前後での prime gap とも読むことができる。
-
探査範囲の最終目標は、n=1300まで(注:1300桁は UBASIC の modpow の計算限界)。
前後の素数については探査完了。
- 表の見方
|
[3] 階乗・素数の積・合成数の積に近い素数
n! に近い素数
(n=1, ... , 561 : Dec. 04, 2008)
#Pn に近い素数
(n=1, ... , 437 : Dec. 12, 2008)
#Compn に近い素数
(n=1, ... , 538 : Dec. 14, 2008)
|
-
n が素数のとき、(n-1)!+1 は n で割り切れる (Wilson の定理)。
また、N=n!±k (k=2, ... ,n) については、Nは自明な約数を持つ。
それ以外については、約数、素数性については不明。
n! (n の階乗 (factorial)) に近い素数を求めた。
modpowの計算限界 n=561 (1300桁) まで計算完了。
-
#Pn は n 番目までの素数の積を表す。
#Pn = P1 * P2 * ... * Pn
階乗 (factorial) からの造語で、primorial と呼ばれることが多い。
#Pn+1 は、Pk (k=1, ... ,n) で割り切れないため、
素数が無数にあることの証明で使われる。
#Pn に近い素数を求めた。
modpowの計算限界 n=437 (Pn=3049, #Pn:1300桁) まで計算完了。
-
階乗 (factorial), 素数の積 (primorial) からの類推で、
合成数の積を compositorial と呼ぶことにする
(注:用語としては定着していない)。
例えば n=10 の時の factorial, primorial, compositorial は以下のようになる。
F : 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
P : 2 * 3 * 5 * 7
C : 4 * 6 * 8 * 9 * 10
Compositorial #Compn は、
#Compn = n! / #Pk
ただし k は、Pk ≤ n となるような最大の数
という式で表すことができる。
#Compn に近い素数を求めた。
modpowの計算限界 n=538 (Cn=658, #Cn:1300桁) まで計算完了。
|
表の見方
[1] n ビットの素数
n が 7 以下の時は、素数の個数が10個に満たないので、そのビット数の素数全てを列挙している。
例えば、
5 | 1, 3, 7, 13, 15
は、
24+1 (=17)
24+3 (=19)
24+7 (=23)
24+13 (=29)
24+15 (=31)
が、5 ビットの素数であることを示す。
n が 8 以上の時は、最初と最後の10個を列挙している。
例えば、
8 | 3, 9, 11, 21, 23, 29, 35, 39, 45, 51 | -59,-57,-45,-33,-29,-27,-23,-17,-15,-5
は、
27+3 (=131)
27+9 (=137)
...
27+45 (=173)
27+51 (=179)
...
...
28-59 (=197)
28-57 (=199)
...
28-15 (=241)
28-5 (=251)
が、8 ビットの素数の最初と最後の10個であることを示す。
[2] 10nに近い素数
last 10 primes nearest to 10^n (form 10^n-a) [n] first 10 primes nearest to 10^n (form 10^n+b)
---------------------------------------------[-]-----------------------------------------------
-8, -7, -5, -3 [1] 1, 3, 7, 9, 13, 19, 21, 27, 31, 33
は、
101-8 (=2)
101-7 (=3)
101-5 (=5)
101-3 (=7)
が、101 より小さく、101 に最も近い素数
(この場合、4個しかないので、4個だけ列挙している)
また、
101+1 (=11)
101+3 (=13)
...
101+31 (=41)
101+33 (=43)
が、101 より大きく、101 に最も近い素数をであることを表している。
Furthur computation
- 最初と最後の10個を modpow の計算限界まで拡張
- APRT-CLE、ECPP を使用した、厳密な primarity check の実施
E-mail : kc2h-msm@asahi-net.or.jp三島 久典