半素數

半素數，也稱為 2-近素數、雙素數 (Conway et al. 2008) 或 -數，是一個合數，它是兩個（可能相等）素數的乘積。前幾個是 4, 6, 9, 10, 14, 15, 21, 22, ... (OEIS A001358)。前幾個因子不同的半素數（即，無平方因子的半素數）是 6, 10, 14, 15, 21, 22, 26, 33, 34, ... (OEIS A006881)。

根據定義，任何素數的平方都是一個半素數。因此，已知的最大半素數是已知最大素數的平方。

小於或等於 的半素數數量的公式由下式給出

(1)

其中 是素數計數函式， 是第 個素數（R. G. Wilson V, 私人通訊，2006 年 2 月 7 日；由 E. Noel 和 G. Panos 在 2005 年 1 月左右獨立發現，私人通訊，2006 年 6 月 13 日）。

小於 的半素數的數量，對於 , 2, ... 分別是 3, 34, 299, 2625, 23378, 210035, ... (OEIS A066265)。

對於 ，其中 和 不同，滿足以下同餘式

(2)

此外，尤拉函式滿足以下簡單恆等式

(3)

透過非將兩個素數相乘的方法生成超過 250 位的可證明半素數是重要的難題。一種方法是因式分解。來自 Cunningham 專案， 和 是已分解的半素數，分別有 274 位和 301 位。類似地，給出半素數的梅森數指數是 4, 9, 11, 23, 37, 41, 49, 59, 67, 83, ... (OEIS A085724)。截至 2022 年，已知的給出半素數的最大指數是 1427 和 1487。

2005 年，Don Reble 展示瞭如何使用橢圓偽曲線和 Goldwasser-Kilian ECPP 定理生成一個 1084 位的可證明半素數，而無需已知的因式分解 (Reble 2005)。Vitto (2021) 隨後發現了一種後門策略，分解了 Reble 的 1084 位半素數，並引入了一種建立半素數證書的新方法，該方法至少與相同大小的隨機半素數一樣安全。

諸如 RSA 加密之類的加密演算法依賴於特殊的大的數字，這些數字的因子是兩個大的素數。下表列出了一些特殊的半素數，它們是兩個大的（不同的）素數的乘積。

	n 的位數	p 的位數	q 的位數
	45	23	23
	49	21	28
	51	22	29
	54	23	32
	54	25	29
	55	25	31
	64	32	32
RSA-129	129	64	65
RSA-140	140	70	70
RSA-155	155	78	78