半素数
数学において、半素数（はんそすう、semiprime あるいは biprime）とは、2つの素数（2つは異ならなくてもよい）の積で表される自然数（合成数）である。
目次 |
[編集] 半素数の例
例えば、91 は 7 × 13 と2つの素数の積に素因数分解されるので半素数である。最も小さい半素数は最小の素数 2 の2乗の 4 である。素数は無限にあるため、半素数も無限個ある。半素数を小さい順に列記すると
となる。
[編集] 生成法
半素数は2つの素数の積であるため、a × b（a, b は2以上の自然数）の形で一意的に表すことができる。したがって、以下のように表の上端と左端に素数を順に並べ（太字）、それぞれの升目から見て上端と左端に書かれている数を掛け合わせればすべての半素数を生成することができる。
| × | 2 | 3 | 5 | 7 | 11 | 13 | … |
|---|---|---|---|---|---|---|---|
| 2 | 4 | 6 | 10 | 14 | 22 | 26 | … |
| 3 | 9 | 15 | 21 | 33 | 39 | … | |
| 5 | 25 | 35 | 55 | 65 | … | ||
| 7 | 49 | 77 | 91 | … | |||
| ： | ： | ： | ： | ： | ： | ： |
[編集] 使用例
半素数は数論や暗号理論（特に公開鍵暗号）では重要な存在であり、例として、RSA暗号やRabin暗号では、桁数が大きな（安全性のために一定の条件を満たす）2個の素数の積が公開鍵として使われている（参考：RSAモジュラス）。2個の素数の積を求めることは容易であるが、この半素数を素因数分解して元の2個の素数を求めることは困難であることが安全性の根拠になっている。 その他、擬似乱数生成器 Blum-Blum-Shubでも同様な半素数を法として初期値を2乗して得られる数列の最下位ビットを乱数列としている。半素数にはブラム数を用いるとよいとされる。ゼロ知識証明で証明対象とされる知識としても、半素数の2個の素因子が利用される。
1974年に送信されたアレシボ・メッセージでは、1,679桁の2進数をメッセージとした。この1679も半素数である。n行m列からなるドットピクセルを0/1に変換して、さらに1列にして送信されたメッセージを、受信側が元のn行m列に戻す際に、n や m を推測し易いように、半素数が選ばれたのである。1679 を素因数分解すると、1679 = 23 x 73 であり、n = 23, m = 73 か n = 73, m =23 のどちらかになる。
[編集] 参考文献
- デイビッド・ウェルズ 『数の事典』 芦ヶ原伸之・滝沢清訳、東京図書、1987年、ISBN 4-489-00242-4。
