半素数

数学において、半素数（はんそすう、英: semiprime, biprime）とは、2つの素数の積で表される合成数である。この2つの素数は同一のものであってもよいため、素数の2乗となる平方数も半素数である。

半素数は概素数の k = 2 の例でもある。

定義

「自然数 n が半素数である」とは、n が素数 p, q の積 pq に等しいことをいう。

性質

• 半素数は無数に存在する（素数が無数に存在することの証明から）
• 最小の半素数は 4 である（最小の素数が 2 であることから）
• 最小の平方数でない半素数は 6 である（2番目の素数が 3 であることから）
• 素数の2乗となる平方数は半素数である（半素数の定義より）
• 半素数 n の約数は 1, p, q, pq である
• 約数の個数は p = q なら3個、p ≠ q なら4個である
• 約数の総和は p = q なら 1 + p + p²、p ≠ q なら 1 + p + q + pq である
• 6 以外の半素数は全て不足数である
  • 4 は不足数である（1 + 2 < 4）
  • 6 は完全数である（1 + 2 + 3 = 6）
  • 6 より大きい半素数は全て不足数である（3 ≤ p ≤ qより、1 + p + q ≤ 1 + 2q < 3q ≤ pq）

例

例えば、15は、15 = 3 × 5 であり 3, 5 はいずれも素数であるから、半素数である。

1から100まで整数に含まれる半素数（斜体は素数の平方数）： 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)

連続する半素数（n, n + 1）の先頭 n：9, 14, 21, 25, 33, 34, 38, 57, 85, 86, 93, 94, … (オンライン整数列大辞典の数列 A070552) （n + 1 の列はオンライン整数列大辞典の数列 A109373を参照）。

異なる素因数からなる半素数：6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, …(オンライン整数列大辞典の数列 A006881)

素数の2乗（平方数）となる半素数：4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, …(オンライン整数列大辞典の数列 A001248)

十進法での半素数の回文数（斜体は平方数）：4, 6, 9, 22, 33, 55, 77, 111, 121, …（オンライン整数列大辞典の数列 A046328）

応用

半素数は数論や暗号理論（特に公開鍵暗号）では重要な存在であり、例として、RSA暗号やRabin暗号では、桁数が大きな（安全性のために一定の条件を満たす）2個の素数の積が公開鍵として使われている。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 のどちらかになる。

脚注

参考文献

• ウェルズ, デイビッド 著、芦ヶ原伸之・滝沢清 訳『数の事典』東京図書、1987年。ISBN 4-489-00242-4。 

関連項目

• 素数
• 楔数
• 概素数
• 素因数分解

外部リンク

• Weisstein, Eric W. "Semiprime". mathworld.wolfram.com (英語).