Loading AI tools
来自维基百科,自由的百科全书
半素數(又稱雙素數,二次殆素數),為兩個素數的乘積所得的自然數。最前面的幾個半素數是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... (OEIS數列A001358)它們包含1及自己在內共有3個或4個因數。[1]
比100小的半素數有:
不是平方數的半素數被稱為離散、特異或非平方半素數,包括:
半素數是的次殆素數(有且僅有個質因數的數)。 但是有些數列將「半素數」解釋為一種更加寬泛的數,即最多有兩個質因數的數[2],包括:
除了自己本身外,半素數沒有其他合數因數。[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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.