半素数
数学において、半素数（はんそすう、英: semiprime, biprime）とは、2 つの素数（2 つは同じでもよい）の積で表される自然数（合成数）である。
半素数の例
例えば、91 は 7 × 13 と 2 つの素数の積に素因数分解されるので半素数である。
最小の半素数は、最小の素数 2 の 2 乗の 4 である。
素数は無数に存在するため、半素数も無数に存在する。半素数を小さい順に列記すると
- 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, …（オンライン整数列大辞典の数列 A1358）
連続で半素数が表れる小さい方の数は
である（大きい方の数についてはオンライン整数列大辞典の数列 A109373を参照）。上記の半素数で連続している数は 3 連続半素数（小さい方の数：オンライン整数列大辞典の数列 A056809）を表している（中央の数はオンライン整数列大辞典の数列 A086005、大きい方の数はオンライン整数列大辞典の数列 A086006を参照）。
また、半素数は、6を除いて不足数である。
生成法
半素数は 2 つの素数の積であるため、p × q（p, q は素数で p ≦ q）の形で一意的に表すことができる。したがって、以下のように表の上端と左端に素数を順に並べ（太字）、それぞれの升目から見て上端と左端に書かれている数を掛け合わせればすべての半素数を生成することができる。
| × | 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年に送信されたアレシボ・メッセージでは、1679桁の2進数をメッセージとした。この 1679 も半素数である。n 行 m 列からなるドットピクセルを 0/1 に変換して、さらに1列にして送信されたメッセージを、受信側が元の n 行 m 列に戻す際に、n や m を推測し易いように、半素数が選ばれたのである。1679 を素因数分解すると、1679 = 23 × 73 であり、n = 23, m = 73 か n = 73, m = 23 のどちらかになる。
半素数の回文数
回文数になるものもある。
( )は同じ素数の2乗。
(4), 6, (9), 22, 33, 55, 77, 111, (121)……[1]
参考文献
- デイビッド・ウェルズ 『数の事典』 芦ヶ原伸之・滝沢清訳、東京図書、1987年、ISBN 4-489-00242-4。
脚注
- ↑ オンライン整数列大辞典の数列 A046328
関連項目
外部リンク
- Weisstein, Eric W. “Semiprime”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。