半素數

半素數（又稱雙素數，二次殆素數），為兩個素數的乘積所得的自然數。最前面的幾個半素數是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... （OEIS數列A001358）它們包含1及自己在內共有3個或4個因數。

例子與種類

比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 （OEIS數列A001358）.

不是平方數的半素數被稱為離散、特異或非平方半素數，包括：

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... （OEIS數列A006881）

半素數是$k=2$的$k$次殆素數（有且僅有$k$個質因數的數）。 但是有些數列將「半素數」解釋為一種更加寬泛的數，即最多有兩個質因數的數，包括：

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... （OEIS數列A037143）

性質

除了自己本身外，半素數沒有其他合數因數。例如，1、2、13及26是半素數26的因數，其中只有26是合數。

對於非平方半素數$n=pq$（$p\neq q$），其歐拉函數的值$\varphi (n)$（小於或等於$n$的正整數中與$n$互質的數的數目）可以用簡單的公式表達：

$\varphi (n)=(p-1)(q-1)=n-(p+q)+1.$

這個公式是RSA加密演算法半素數應用的重要部分。對於一個平方半素數，該公式又會簡化為：

$\varphi (n)=p(p-1)=n-p.$

應用

半素數在密碼學和數論中非常有用，最顯著的例子的是RSA加密演算法和隨機數發生器等公開密鑰加密應用。這些應用的基本原理是，計算兩素數相乘結果（一個半素數）的過程簡單，而反過來整數分解大半素數則比較困難。簡單的來說，雖然35很容易就可以被分解成5×7，但是要想分解很大的半素數就不是那麼容易了。RSA加密演算法中有一個稱為RSA-2048的半素數，有2,048位元，十進位有617位，RSA曾經公開懸賞200,000美元，給予成功將RSA-2048因數分解的人，迄2007年活動終止，未有人挑戰成功領取懸賞。

1974年，阿雷西博信息通過無線電信號被發向星團。其由1679個二進制數字組成，這些數字的用意是讓接收方將信息解析成位圖圖像。選擇數字$1679=23\cdot 73$是因為其是一個半素數，只存在一種構成矩形圖像的可能（up to 圖像平面的旋轉和反射）。

另見

• 陳氏定理

外部連結

• 埃里克·韋斯坦因. Semiprime. MathWorld. 
• 前10000個半質數（頁面存檔備份，存於網際網路檔案館）