半質數

半質數 圖片來自newton

數學中，兩個素數的乘積所得的自然數我們稱之為半素數（也叫雙素數，二次殆素數 ）。開始的幾個半素數是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... id=A001358它們包含1及自己在內合共有3或4個因數。

目錄

性質

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

對於非平方半素數n=pq（p\ne 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個二進制數字組成，這些數字的用意是讓接收方將信息解析成位圖圖像。選擇數字<math>1679=23\cdot 73</math>是因為其是一個半素數，只存在一種構成矩形圖像的可能（up to 圖像平面的旋轉和反射）。

例子與種類

比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 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, ... A006881

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

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, ... A037143