半素数

半素数（又称双素数，二次殆素数），为两个素数的乘积所得的自然数。最前面的几个半素数是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... （OEIS数列A001358）它们包含1及自己在内共有3个或4个约数。

例子与种类

比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）

半素数是$k=2$的$k$次殆素数（有且仅有$k$个素因数的数）。 但是有些数列将“半素数”解释为一种更加宽泛的数，即最多有两个素因数的数，包括：

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）

性质

除了自己本身外，半素数没有其他合数因数。例如，1、2、13及26是半素数26的因数，其中只有26是合数。

对于非平方半素数$n=pq$（$p\neq q$），其欧拉函数的值$\varphi (n)$（小于或等于$n$的正整数中与$n$互质的数的数目）可以用简单的公式表达：

$\varphi (n)=(p-1)(q-1)=n-(p+q)+1.$

这个公式是RSA加密算法半素数应用的重要部分。对于一个平方半素数，该公式又会简化为：

$\varphi (n)=p(p-1)=n-p.$

应用

半素数在密码学和数论中非常有用，最显著的例子的是RSA加密算法和随机数发生器等公开密钥加密应用。这些应用的基本原理是，计算两素数相乘结果（一个半素数）的过程简单，而反过来整数分解大半素数则比较困难。简单的来说，虽然35很容易就可以被分解成5×7，但是要想分解很大的半素数就不是那么容易了。RSA加密算法中有一个称为RSA-2048的半素数，有2,048位元，十进制有617位，RSA曾经公开悬赏200,000美元，给予成功将RSA-2048约数分解的人，迄2007年活动终止，未有人挑战成功领取悬赏。

1974年，阿雷西博信息通过无线电信号被发向星团。其由1679个二进制数字组成，这些数字的用意是让接收方将信息解析成位图图像。选择数字$1679=23\cdot 73$是因为其是一个半素数，只存在一种构成矩形图像的可能（up to 图像平面的旋转和反射）。

另见

• 陈氏定理

外部链接

• 埃里克·韦斯坦因. Semiprime. MathWorld. 
• 前10000个半素数（页面存档备份，存于互联网档案馆）