半素数是按重数计恰好为两个素数之积的正整数。也就是说,若 n=pq,其中 p 和 q 均为素数且可以相同,则 n 是半素数。半素数是数论的研究对象,在密码学中也具有重要作用:两个大素数的乘积可用作 RSA 等密码系统的模数。
定义与示例
半素数按从小到大的顺序排列,开头若干项为
4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69,…
例如:
- 4=22 和 49=72 是半素数,因为重复出现的素因子要计数两次。
- 6=2⋅3 和 35=5⋅7 是具有两个不同素因子的半素数。
- 12=22⋅3 不是半素数:按重数计,它有三个素因子。
- 1 和任何素数都不是半素数。
算术基本定理保证了这一定义没有歧义。若 n>1 的素因数分解为
n=p1a1p2a2⋯prar
则定义
Ω(n)=a1+a2+⋯+ar.
于是,n 是半素数当且仅当 Ω(n)=2。
因此,半素数是殆素数在 k=2 时的特例;殆素数是指按重数计恰好有 k 个素因子的整数。不过,筛法中的某些术语指的是至多有 k 个素因子的整数,因此在这类语境下必须核实所采用的约定。
类型与基本性质
半素数分为两类:
| 类型 |
形式 |
示例 |
正因数个数 |
| 素数的平方 |
p2 |
25=52 |
3 |
| 两个不同素数的乘积 |
pq, p=q |
35=5⋅7 |
4 |
具有两个不同素因子的半素数是无平方因子整数,其正因数恰为 1,p,q,pq。而素数的平方的正因数则为 1,p,p2。
仅凭有四个正因数,并不能判定一个数是半素数:p3 也恰好有四个正因数,但按重数计有三个素因子。
偶半素数恰好是形如 2p 的数,其中 p 为素数。每个奇半素数都是两个奇素数的乘积。半素数有无穷多个,因为素数有无穷多个,而每个素数 p 都对应一个不同的半素数 2p。
欧拉函数统计不超过 n 且与 n 互素的正整数的个数。对于两个不同素数的乘积,有
φ(pq)=(p−1)(q−1)(p=q),
而对于素数的平方,则有
φ(p2)=p(p−1).
这一区别至关重要:适用于两个不同素因子的公式不能用于素数的平方。
计数与分布
设 S(x) 表示不超过 x 的半素数的个数,π(x) 表示不超过 x 的素数的个数,并用 pi 表示第 i 个素数。一个精确的计数公式为
S(x)=i=1∑π(x)[π(pix)−i+1].
为推导这一公式,将每个半素数唯一地写成 pipj,其中 i≤j。它的较小素因子不超过 x;固定 pi 后,可选的较大素因子满足
pi≤pj≤pix.
求和式中的每一项统计的就是这些选择的个数,其中包括 pj=pi 的情形。
一个经典的渐近结果,即朗道关于殆素数的定理在 k=2 时的情形,指出
S(x)∼logxxloglogx(x→∞),
其中 log 表示自然对数,∼ 表示两边的比值趋于 1。
因此,半素数的自然密度为零:
x→∞limxS(x)=0.
不过,与素数定理比较可得
π(x)S(x)∼loglogx.
所以,随着上界增大,半素数的累计个数与素数个数之比最终会超过任意给定的界限。
素数的平方对 S(x) 的贡献仅为 π(x),其所占比例在渐近意义下可以忽略。因此,在这种计数意义下,几乎所有半素数都具有两个不同的素因子。
判定与因数分解
如果已知一个整数的完整素因数分解,就能立即判定它是否为半素数:各素因子指数之和必须等于二。反过来,若给出了分解式 n=pq,只要两个因子都通过素性检验,便可确认 n 是半素数。
一种直接的判定方法是试除不超过 n 的所有可能的素因子。若最小素因子为 p,则 n 是半素数当且仅当 n/p 是素数。这种方法对小整数很实用,但若以输入整数的位数衡量效率,则对大整数而言效率很低。
在整数分解中,两个素因子大小相近的大半素数尤其重要。含有较小因子的半素数通常可以很快分解;因此,仅凭一个数是半素数,并不能推断其分解具有多大的计算难度。
在密码学中的作用
在标准的双素数 RSA密码系统中,公开的模数为
其中 p 和 q 是两个不同的大素数。这两个因子需要保密,而加密和签名运算则使用以 n 为模的模算术。
知道 p 和 q 就能计算 φ(n),进而在通常的 RSA 条件下,根据公钥指数求出私钥指数。对于由两个不同素数相乘得到的半素数,知道 φ(n) 也能求出这两个因子,因为
p+q=n−φ(n)+1.
这两个素数就是下列二次方程的根:
t2−(n−φ(n)+1)t+n=0.
因此,分解模数便能破解标准 RSA。然而,一般的 RSA 求逆问题尚未被证明与因数分解等价。安全性还取决于密钥生成、填充方式和具体实现,而不只是模数是否为半素数。