Appendix 5. 素数表(各桁・ビット数の最大/最小の素数)

(2009/01/18) [English]

概要

n 桁の素数を生成したい場合、もっとも primitive な方法は、

まず、ランダムに n 桁の奇数を生成して素数判定を行い、
だめな場合は、2を足してまた素数判定、

という手順を繰り返す方法である。

ランダムに数を選ぶと、ほとんどの場合、合成数となるので(かつ、小さい約数を持つ場合が多いので)、 いきなり厳密な素数判定を行うのではなく、 まず小さい数(3, 5, 7)で割り切れるかどうかをチェックし、 次に、フェルマーテストでフィルターをかける。
これでほとんどの合成数は、ふるい落とされるので、 残った数に対して、もう少し厳密な素数判定を行う。

この方法により、

を探してみる。

探査の個数は、それぞれの n について、

とする。

素数判定は、Solovey-Strassen test で、base が 2, 3, 5, 7, 11, 13, 17, 19 の場合をチェック。
(よって、正確には素数ではなく probable prime だが、 この判定で素数と判定され、実際は合成数、
ということは、極めて稀。もし見つかればニュースになる。)
正確には、いずれ、APRT-CLE、ECPP等でまじめにチェックする必要がある。

素数表

[1] n ビットの素数
  • n ビットの数 N は、2n-1 ≤ N ≤ 2n-1 の範囲内にある。
    この範囲内の素数を、小さい方(2n-1に近い方)、及び、
    大きい方(2n-1)から求める。
    これは、2n の前後の素数、とも読み替えることができる。
    これらの値は、公開鍵暗号等で、鍵生成を行う場合に有用となる。

  • 表の見方
[2] 10nに近い素数
  • 10n の前後の素数を求める。
    この結果は、各桁数の最小・最大の素数とも読み替えることができる。
    また、10n の前後での prime gap とも読むことができる。

  • 探査範囲の最終目標は、n=1300まで(注:1300桁は UBASIC の modpow の計算限界)。
    前後の素数については探査完了。

  • 表の見方
[3] 階乗・素数の積・合成数の積に近い素数

  • 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


  数学者の密室
目次
 

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典