跳至內容

半質數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

半質數(又稱雙質數二次殆質數),為兩個質數的乘積所得的自然數。最前面的幾個半質數是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

半質數是殆質數(有且僅有個質因數的數)。 但是有些數列將「半質數」解釋為一種更加寬泛的數,即最多有兩個質因數的數[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是合數。

對於非平方半質數),其歐拉函數的值(小於或等於的正整數中與互質的數的數目)可以用簡單的公式表達:

這個公式是RSA加密演算法半質數應用的重要部分。[4]對於一個平方半質數,該公式又會簡化為:[4]

應用

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

1974年,阿雷西博資訊通過無線電信號被發向星團。其由1679個二進制數字組成,這些數字的用意是讓接收方將資訊解析成位圖圖像。選擇數字是因為其是一個半質數,只存在一種構成矩形圖像的可能(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. ^ 4.0 4.1 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). 

外部連結