半素数

数学において、半素数（はんそすう、英: 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個、 $p \neq q$ なら4個である
約数の総和は $p = q$ なら $1 + p + p 2$ 、 $p \neq q$ なら $1 + p + q + pq$ である
6 以外の半素数は全て不足数である
- 4 は不足数である（ $1 + 2 < 4$ ）
- 6 は完全数である（ $1 + 2 + 3 = 6$ ）
- 6 より大きい半素数は全て不足数である（ $3 \leq p \leq q$ ^{[注釈 3]}より、 $1 + p + q \leq 1 + 2 q < 3 q \leq pq$ ）

例

例えば、 $15$ は、 $15 = 3 \times 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 のどちらかになる。

脚注

[脚注の使い方]

注釈

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

出典

参考文献

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

外部リンク

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

[1] 半素数に類似した概念に楔数があるが、これは「"相異なる"3つの素数の積」として定義されるため、平方因子をもたない整数であり、立方数になることもない。

[2] $k$ -概素数を「素因数分解の指数の和が $k$ に等しい自然数」と定義した場合。

[3] ここで $p \leq q$ としても一般性を失わない。 $3 \leq p$ は $6 < pq$ より得られる。

[注釈 1]

[注釈 2]

[注釈 3]

表話編歴素数の分類
生成式	フェルマー ( $2 2 n + 1$ ) メルセンヌ ( $2 p - 1$ ) 二重メルセンヌ ( $2 2 p -1 - 1$ ) ワグスタッフ ( $(2 p + 1)/3$ ) プロス ( $k \cdot2 n + 1$ ) 階乗 ( $n! \pm 1$ ) 素数階乗 ( $p n # \pm 1$ ) ユークリッド ( $p n # + 1$ ) ピタゴラス ( $4 n + 1$ ) ピアポント ( $2 u \cdot3 v + 1$ ) Quartan（英語版） ( $x 4 + y 4$ ) ソリナス（英語版） ( $2 a \pm 2 b \pm 1$ ) カレン ( $n \cdot2 n + 1$ ) ウッダル ( $n \cdot2 n - 1$ ) Cuban（英語版） ( $(x 3 - y 3)/(x - y)$ ) キャロル ( $(2 n - 1) 2 - 2$ ) Kynea ( $(2 n + 1) 2 - 2$ ) レイランド ( $x y + y x$ ) サービト（英語版） ( $3\cdot2 n - 1$ ) ミルズ ( $[A] 3 n$ )
漸化式（英語版）	フィボナッチリュカペルニューマン–シャンクス–ウィリアムズペラン分割ベルモツキン
各種の性質	ヴィーフェリッヒ（英語版） (対（英語版）) ウォール–孫–孫（英語版）ウォルステンホルムウィルソン幸運フォーチュンラマヌジャン（英語版）ピライ正則強（英語版）スターン Supersingular (楕円曲線)（英語版） Supersingular (ムーンシャイン理論)（英語版）良いスーパーヒッグス（英語版）高度コトーティエント（英語版）
基数依存	ハッピー二面（英語版）回文エマープレピュニット ( $(10 n - 1)/9$ ) 置換可能 Circular（英語版）切り捨て可能 Strobogrammatic（英語版） Minimal（英語版）弱いフルサイクルプライム Unique（英語版） Primeval（英語版）自己スマランダチェ–ウェラン（英語版）
組	互いに素双子 ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) 三つ子 ( $p, p + 2$ or $p + 4, p + 6$ ) 四つ子 ( $p, p + 2, p + 6, p + 8$ ) k−Tuple いとこ ( $p, p + 4$ ) セクシー ( $p, p + 6$ ) 陳ソフィー・ジェルマン ( $p, 2 p + 1$ ) カニンガム鎖 ( $p, 2 p \pm 1, \dots$ ) 安全 ( $p, (p - 1)/2$ ) 算術数列（英語版） ( $p + an; n = 0, 1, \dots$ ) 平衡 ( $p - n, p, p + n$ )
桁数	タイタニック ( $103$ 桁以上) 巨大 ( $104$ 桁以上) メガ ( $106$ 桁以上)
複素数	アイゼンシュタイン素数（英語版）ガウス素数
合成数	擬素数概素数半素数楔数 Interprime（英語版）
関連する話題	確率的素数 Industrial-grade prime（英語版）違法素数素数の公式（英語版）素数の間隔『巨大な素数の一覧』
最初の50個	$2$ $3$ $5$ $7$ $11$ $13$ $17$ $19$ $23$ $29$ $31$ $37$ $41$ $43$ $47$ $53$ $59$ $61$ $67$ $71$ $73$ $79$ $83$ $89$ $97$ $101$ $103$ $107$ $109$ $113$ $127$ $131$ $137$ $139$ $149$ $151$ $157$ $163$ $167$ $173$ $179$ $181$ $191$ $193$ $197$ $199$ $211$ $223$ $227$ $229$
素数の一覧

表話編歴被整除性に基づいた整数の集合
概要	素因数分解約数単約数約数関数素因数算術の基本定理
因数分解による分類	素数合成数半素数矩形数楔数平方因子をもたない整数多冪数累乗数アキレス数滑らかな数（英語版）ハミング数（英語版）粗い数（英語版）異常数（英語版）
約数和による分類	完全数概完全数準完全数倍積完全数 Hemiperfect number（英語版）ハイパー完全数超完全数単完全数（英語版）擬似完全数プラクティカル数エルデシュ・ニコラス数（英語版）
約数が多いもの	過剰数原始過剰数（英語版）高度過剰数超過剰数巨大過剰数高度合成数優高度合成数（英語版）不思議数
アリコット数列関連	アンタッチャブル数（英語版）友愛数 (友愛三数（英語版）) 社交数婚約数
位取り記法に基づくもの	Equidigital number（英語版） Extravagant number（英語版） Frugal number（英語版）ハーシャッド数 Polydivisible number（英語版）スミス数
その他	Arithmetic number（英語版）不足数 Friendly number（英語版） Solitary（英語版）サブライム数調和数デカルト数（英語版）タウ数超完全数

定義

性質

例

応用

脚注

注釈

出典

参考文献

関連項目

外部リンク