半素数

数論において、半素数とは、ちょうど2つの素数の積である自然数のことです。積に含まれる2つの素数は互いに等しい場合もあるため、半素数には素数の平方も含まれます。素数は無限に存在するため、半素数も無限に存在します。^半素数は、2つの^素数、つまり2番目の^数を含む^ことから、^2つの素

100未満の半素数は次のとおりです。

平方数ではない半素数は、離散半素数、異なる半素数、または平方因子を持たない半素数と呼ばれます。

半素数の場合${\displaystyle k=2}$の${\displaystyle k}$-ほぼ素数、ちょうど${\displaystyle k}$素因数。ただし、一部の資料では「半素数」をより大きな数の集合、つまり最大で2つの素因数を持つ数（1、素数、半素数を含む）を指すために使用しています。^{[ 4 ]}これらは次のとおりです。

させて$\displaystyle \pi _{2}(n)$n以下の半素数の個数をで表す。すると$${\displaystyle \pi _{2}(n)=\sum _{k=1}^{\pi \left({\sqrt {n}}\right)}\left[\pi \left({\frac {n}{p_{k}}}\right)-k+1\right]}$$ どこ${\displaystyle \pi (x)}$は素数計数関数であり、${\displaystyle p_{k}}$k番目の素数を表す。 ^{[ 5 ]}

これを見るには、${\displaystyle p_{k}}$より小さい素因数となる。${\displaystyle p_{k}\leq {\sqrt {n}}}$そして、より大きな因数は任意の素数である可能性がある。${\displaystyle q}$満足${\displaystyle p_{k}\leq q\leq n/p_{k}}$このような素数の数は${\displaystyle \pi (n/p_{k})-\pi (p_{k}-1)}$。 以来${\displaystyle p_{k}}$k番目の素数です。${\displaystyle \pi (p_{k}-1)=k-1}$命令を与える${\displaystyle \pi (n/p_{k})-k+1}$。

半素数は、自分自身以外の合成数を因数として持ちません。 ^{[ 6 ]}例えば、26は半素数であり、その因数は1、2、13、26のみで、そのうち合成数は26だけです。

平方因子を持たない半素数の場合${\displaystyle n=pq}$（と${\displaystyle p\neq q}$オイラーのトーシェント関数の値${\displaystyle \varphi (n)}$（${\displaystyle n}$比較的優良な${\displaystyle n}$) は単純な形式をとる $${\displaystyle \varphi (n)=(p-1)(q-1)=n-(p+q)+1.}$$この計算は、 RSA暗号システム における半素数の応用の重要な部分です。^{[ 7 ]} 平方半素数の場合${\displaystyle n=p^{2}}$式は再び単純です: ^{[ 7 ]}$${\displaystyle \varphi (n)=p(p-1)=np.}$$

半素数は、暗号学や数論の分野で非常に有用であり、特に公開鍵暗号では、RSAやBlum Blum Shubなどの擬似乱数生成器で使用されています。これらの方法は、2つの大きな素数を見つけて掛け合わせる（結果として半素数が得られる）ことは計算上簡単であるのに対し、元の因数を見つけるのは難しいという事実に基づいています。RSAファクタリングチャレンジでは、RSA Securityが特定の大きな半素数の因数分解に対して賞金を提供し、いくつかの賞が授与されました。オリジナルのRSAファクタリングチャレンジは1991年に発行され、2001年に新しいRSAファクタリングチャレンジに置き換えられましたが、2007年に撤回されました。^{[ 8 ]}

1974年、アレシボメッセージは星団に向けた無線信号とともに送信された。それは${\displaystyle 1679}$バイナリ数字は、$23×73$ビットマップ画像。${\displaystyle 1679=23\cdot 73}$が選ばれたのは、それが半素数であるため、長方形の画像に配置できる方法が 2 つしかないからである (23 行 73 列、または 73 行 23 列)。^{[ 9 ]}

• 陳の定理
• スフェニック数とは、3つの異なる素数の積である。
• パリティ問題（篩理論）

• ワイススタイン、エリック W. 「半素数」 . MathWorld .