半素数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

数学において、半素数(はんそすう、: 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

連続で半素数が表れる小さい方の数は

9, 14, 21, 25, 33, 34, 38, 57, 85, 86, 93, 94, …(オンライン整数列大辞典の数列 A070552

である(大きい方の数についてはオンライン整数列大辞典の数列 A109373を参照)。上記の半素数で連続している数は 3 連続半素数(小さい方の数:オンライン整数列大辞典の数列 A056809)を表している(中央の数はオンライン整数列大辞典の数列 A086005、大きい方の数はオンライン整数列大辞典の数列 A086006を参照)。

また、半素数は、6を除いて不足数である。

生成法[編集]

半素数は 2 つの素数の積であるため、p × qp, q は素数で pq)の形で一意的に表すことができる。したがって、以下のように表の上端と左端に素数を順に並べ(太字)、それぞれの升目から見て上端と左端に書かれている数を掛け合わせればすべての半素数を生成することができる。

× 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 も半素数である。nm 列からなるドットピクセルを 0/1 に変換して、さらに1列にして送信されたメッセージを、受信側が元の nm 列に戻す際に、nm を推測し易いように、半素数が選ばれたのである。1679 を素因数分解すると、1679 = 23 × 73 であり、n = 23, m = 73 か n = 73, m = 23 のどちらかになる。

参考文献[編集]

関連項目[編集]

外部リンク[編集]