半質數

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

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

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）

性質

除了自己本身外，半質數沒有其他合數因數。^[3]例如，1、2、13及26是半質數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加密演算法半質數應用的重要部分。^[4]對於一個平方半質數，該公式又會簡化為：^[4]

${\displaystyle \varphi (n)=p(p-1)=n-p.}$

應用

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

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

另見

• 陳氏定理

參考資料與附註

1. Sloane, N.J.A. (編). Sequence A001358. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
2. Stewart, Ian. Professor Stewart's Cabinet of Mathematical Curiosities. Profile Books. 2010: 154 [2018-07-14]. ISBN 9781847651280. （原始內容存檔於2021-04-28）.
3. French, John Homer. Advanced Arithmetic for Secondary Schools. New York: Harper & Brothers. 1889: 53.
4. Cozzens, Margaret; Miller, Steven J., The Mathematics of Encryption: An Elementary Introduction, Mathematical World 29, American Mathematical Society: 237, 2013 [2018-07-14], ISBN 9780821883211, （原始內容存檔於2019-07-22）
5. The RSA Factoring Challenge. [2012-08-04]. （原始內容存檔於2013-07-27）.
6. du Sautoy, Marcus. The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. 2011: 19 [2018-07-14]. ISBN 9780230120280. （原始內容存檔於2021-04-28）.

外部連結

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