半素数 -- 来自 Wolfram MathWorld

半素数

半素数，也称为 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

参考资料

Conway, J. H.; Dietrich, H.; O'Brien, E. A. "Counting Groups: Gnus, Moas, and Other Exotica." Math. Intell. 30, 6-18, 2008.

Goldston, D. A.; Graham, S. W.; Pintz, J. and Yildirim, Y. "Small Gaps Between Primes or Almost Primes." 3 Jun 2005. http://arxiv.org/abs/math.NT/0506067.

Sloane, N. J. A. Sequences A001358/M3274, A0068814082, A066265, and A085724 in "The On-Line Encyclopedia of Integer Sequences."

Vitto, G. "Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes." Cryptology ePrint Archive Paper 2021/1610, 2021. https://eprint.iacr.org/2021/1610.

半素数

另请参阅

使用 Wolfram|Alpha 探索

参考资料

在 Wolfram|Alpha 中被引用

引用为

主题分类