半素数：定義、例、性質と暗号理論における役割

基本的性質

半素数の約数構造は限られている。n = p2 が素数の平方である場合、正の約数は 1、p、n のちょうど3個である。n = p×q かつ p ≠ q の場合、正の約数は 1、p、q、n のちょうど4個である。素因数を重複度込みで数えるなら、半素数は素因数の総数が2である整数、すなわち通常 Ω(n)=2 と表される整数に正確に一致する。

歴史と暗号理論における役割

半素数の算術は、解析的数論および乗法的数論において長く研究されてきた。現代の計算機科学では、多くの公開鍵暗号方式が大きな半素数を因数分解することの実用上の困難さに依存しているため重要である。たとえばRSA暗号は、2つの大きな素数の積からなる法を用いる。その安全性に関する仮定は、この積から2つの素因数を復元することが計算上困難であるというものである。背景については、暗号理論に関する一般的な解説も参照されたい。

特別な類と区別

半素数の特定の部分類は、暗号学的または理論的な理由から区別される。たとえばブルム整数は、p と q が異なり、いずれも 4 を法として 3 と合同である素数の場合の半素数 p×q である。このような数は、一部のプロトコルで利用される特別な代数的性質をもつ。また、約数がちょうど2個の素数、および素因数が2個を超える高次の k-概素数と半素数を区別することも有用である。

計算と因数分解

与えられた大きな整数が半素数かどうかを判定するには、その素因数を見つけるか、素因数が2個より多いか少ないことを証明する必要がある。単純な方法には試し割りや輪ふるいがあり、大規模な事例にはより高度な因数分解アルゴリズムが用いられる。半素数の研究は、初等的な約数に関する事実を、数論における分布やアルゴリズム的複雑性についてのより深い問題へと結び付ける。背景としては数論の資料、整数の基本算術などの素因数分解の入門資料、または一般的な乗法的構造を参照できる。素数と因数分解に関する追加の参考文献や概説は、標準的な書籍および理論のオンライン入門で利用できる。