半素数

ふたつの素数の積で表される自然数。ふたつの素数は同一でもよい。

数学において、半素数(はんそすう、: semiprime, biprime)とは、2つの素数で表される合成数である。この2つの素数は同一のものであってもよいため、素数の2乗となる平方数も半素数である[注釈 1]

半素数は概素数k = 2 の例でもある[注釈 2]

定義

編集

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

性質

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

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

脚注

編集

注釈

編集
  1. ^ 半素数に類似した概念に楔数があるが、これは「"相異なる"3つの素数の積」として定義されるため、平方因子をもたない整数であり、立方数になることもない。
  2. ^ k-概素数を「素因数分解の指数の和が k に等しい自然数」と定義した場合。
  3. ^ ここで pq としても一般性を失わない3 ≤ p6 < pq より得られる。

出典

編集

参考文献

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

関連項目

編集

外部リンク

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