素数の特徴
素数は不思議な数です。多くの人が素数の魅力に取りつかれて考察し，数学の世界に多くの成果を残してこられました。
人々の活躍の詳細については，たとえば，2つの書籍 [1, 2] に紹介されている。
素数（p）は，自明な約数である「1および自分（p）」でしか割り切れない数です。
自明な約数以外の約数である「真の約数」を持たない数で，p = 1 × p 以外の因数の形を持たない数です。
つまり，自分（p）より小さな数の積では表わせない数であり，一方，素数を組み合わせて他のあらゆる数を作る基になる数です。
この点，京都コンピュータ学院と京都情報大学院大学のスローガンである“No.1 & the Only One”を表わす数です。
自分でしか割り切れないということは“the Only One”を表わします。
また，{素数pと，pより大きな素数}の積となる数のグループで最初になる点で，“No.1”となる数です。
たとえば，素数p=41は，41でしか割り切れないし，数のグループ{41, 41×41, 41×43, 41×47, 41×53, …}の最初になる数です。
これは，自分が，自分と自分のグループを理解することから始まる意味を持っています。そして，自分より大きな数が「素数であるかどうか」を判定するときに一役を果たします。
素数を求めて
数Nより小さなすべての素数を見付ける方法のひとつに，「エラストテネスの篩い」がある。その手順は次のように表わせる。
1. ビット配列 pr[1:N]を用いて，数Nまでの素数の候補を表わす。初期値はすべてオン（1）とする。
2. 数p=2から始めて，pのすべての倍数のpr値をオフ（0）にして，素数の候補から取り除く。
3. 数pが，(p×p) > Nとなるまで，手順2を繰り返す。
4. pr 値がオン（1）になっている数が，数Nまでの素数になる。
たとえば，N=100までに25個の素数がある。
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
素数の中で，値が2だけ違う素数の対は，双子素数と呼ばれている。
数N=100までには，6組の双子素数がある。
[11, 13] [17, 19] [29, 31] [41, 43] [59, 61] [71, 73]
とくに，[41と43]の組を「良い・読み」と覚えています。
少し大きな双子素数に[1,000,037, 1,000,039]がある。
また，51,090桁の双子素数[33,218,925×2169,690±1]が，2002年にコンピュータで計算されたことが報告されている。[3, p.33]
素数に関する公式はあるか
さて，何故，「エラストテネスの篩い」の方法や，それに基づく方法が使われるのでしょうか。
それは，次の2点を解決する公式や計算式がまだ見付かっていないことによります。
問題1. 数Nまでに何個の素数があるか。π(N)
問題2. 数2から数えて，K番目の素数は何か。prime[K]
この問題を解決しようとして，多数の人達が挑戦して，数学上の多くの概念に貢献されてきた[1, 2]。数列，無限級数，e やπとの関係，対数，そして，リーマンのゼータ関数などがある [1,p107]。
ゼータ関数は，ζ(s) = Σn=1∞ (1 / ns) = 1 + 1/2s +1/3s + 1/4s + … で定義され，
ζ(2) = π2 / 6 であると示されている [1, p.93]。
「数 N より小さな素数の個数を表わす一般則あるいは公式はあるか」というリーマンの推測 [2, p.15]から，「ゼータ関数の自明でない零点の実数部はすべて1/2 である」というリーマン予想が出されている [2, p.17]。
それは，現在も未解決のまま引き継がれている。
その解に近いものとして，次の素数定理とその帰結が，ほぼ良いものとして，受け入れられているようです [2, p70-71]。
素数定理：π(N) ～ N / log N （記号“～”は近似を表す）
素数定理からの帰結：
N が素数である確率は ～ 1 / log N
K 番目の素数 ～ K log K
コンピュータの働き
素数の計算と素数の性質の検証には，コンピュータが大いに貢献している。
たとえば，次のような傾向と結果が導かれている。
（1）数107の前後，幅100 の素数の個数は，同じではない。[1, p.16]
9,999,901 907 929 931 937 943 971 973 991（前は9個）
10,000,019 079 （後ろは2個）
（2）数N までの素数の個数π(N) と，素数の平均間隔（N /π(N)）。
[1, p.77 & p.137][2, p.60 & 64]
平均間隔は，Nの103 毎に，およそ7ずつ増えている。
| N | π(N) | 平均間隔 |
| 109 | 50,847,534 | 19.6666 |
| 1012 | 37,607,912,018 | 26.5901 |
| 1015 | 29,844,570,422,669 | 33.5069 |
| 1018 | 24,739,954,287,740,860 | 40.4204 |
逆に，K番目の素数prime[K]を求める。これは，1語32ビットの範囲で，少し以前に求めたもので，現在だと，もっと短時間で求まるでしょう。
| K | Prime[K] | 計算時間 秒 |
| 105 | 1,299,721 | 06.584 |
| 106 | 15,485,867 | 0176.025 |
| 107 | 179,424,691 | 4927.973 |
| 99,940,770 | 2,036,804,591 | 141410.812 (39.28時間) |
1語64ビットの範囲ではどのようになるでしょうか。是非，試してください。
（3）(225,964,951 - 1)が，7,816,230桁の素数であることが，2005年2月18日にドイツで発見された。 [1, p.315]
(2M -1)が素数であるものは，メルセンヌ素数といわれる。
新しくは，(232,582,657 - 1)が9,808,358 桁の素数候補として，2006年9月4日に報じられている。 http://ja.wikipedia.org/wiki/メルセンヌ数。
（4）メルセンヌ数 (267 - 1) は，2つの素数の積，193,707,721 × 761,838,257,287 であることが示された。（1903年）[1,p.336]
この結果は，2つの素数（P, Q）の積に基づくRSA暗号化システムに発展する（Ron Rivest，Adi Shamir，Leonard Adleman，1997年）。
これは，PとQの積Mを求めるのは簡単だが，逆に，大きな数Mを2つの素数に因数分解することは困難であることを基盤にしている。そこでは，法計算（modulo）が利用されている。
RSAは，公開鍵暗号方式（1976年，Whitfield Diff & Martin E. Hellman）のひとつとして良く知られている。[1, p341]
量子計算への発展
大きな数Nの因数分解は計算時間がかかるという点が，RSAの核心になっている。
しかし，量子コンピュータを用いた量子計算では，短時間で解けてしまうかも知れないという「Shorの因数分解アルゴリズム」が提案されている。それは，法計算の周期性と，量子計算の重ね合わせの性質を活かしたものです。
Shorのアルゴリズムを，現在のコンピュータを用いて模擬計算しても，その特徴を充分に発揮することができる。
素数の世界は果てしなく拡がっていく。
- [1] Marcus du Sautoy, The Music of the Primes, 2003,
- マーカス・デュ・ソートイ著（冨永 星 訳）,
素数の音楽, 新潮社, 2005年8月30日，2,400円. - [2] John Derbyshire, Prime Obsession, 2003,
- ジョン・ダービーシャー著（松浦俊輔 訳）,
素数に憑かれた人たち, 日経BP社, 2004年8月30日，2,600円. - [3] Keith Devlin, The Millennium Problems, 2002,
- キース・デブリン著（山口純一 訳）,
興奮する数学, 岩波書店, 2004年8月25日, 2,940円.
渡邉 勝正