aiwiki.page
中文
数学 / 代数与数论 / semiprime

半素数

半素数是恰好由两个素数相乘得到的正整数,这两个素数可以相同。

14 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
素数整数数论算术基本定理欧拉函数自然对数素数定理素性检验半素数

半素数是按重数计恰好为两个素数之积的正整数。也就是说,若 n=pqn=pq,其中 pp 和 qq 均为素数且可以相同,则 nn 是半素数。半素数是数论的研究对象,在密码学中也具有重要作用:两个大素数的乘积可用作 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,\ 6,\ 9,\ 10,\ 14,\ 15,\ 21,\ 22,\ 25,\ 26,\ 33,\ 34,\ 35,\ 38,\ 39,\ 46,\ 49,\ 51,\ 55,\ 57,\ 58,\ 62,\ 65,\ 69,\ldots

例如:

  • 4=224=2^2 和 49=7249=7^2 是半素数,因为重复出现的素因子要计数两次。
  • 6=2⋅36=2\cdot3 和 35=5⋅735=5\cdot7 是具有两个不同素因子的半素数。
  • 12=22⋅312=2^2\cdot3 不是半素数:按重数计,它有三个素因子。
  • 11 和任何素数都不是半素数。

算术基本定理保证了这一定义没有歧义。若 n>1n>1 的素因数分解为

n=p1a1p2a2⋯prarn=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}

则定义

Ω(n)=a1+a2+⋯+ar.\Omega(n)=a_1+a_2+\cdots+a_r.

于是,nn 是半素数当且仅当 Ω(n)=2\Omega(n)=2。

因此,半素数是殆素数在 k=2k=2 时的特例;殆素数是指按重数计恰好有 kk 个素因子的整数。不过,筛法中的某些术语指的是至多有 kk 个素因子的整数,因此在这类语境下必须核实所采用的约定。

类型与基本性质

半素数分为两类:

类型 形式 示例 正因数个数
素数的平方 p2p^2 25=5225=5^2 3
两个不同素数的乘积 pqpq, p≠qp\ne q 35=5⋅735=5\cdot7 4

具有两个不同素因子的半素数是无平方因子整数,其正因数恰为 1,p,q,pq1,p,q,pq。而素数的平方的正因数则为 1,p,p21,p,p^2。

仅凭有四个正因数,并不能判定一个数是半素数:p3p^3 也恰好有四个正因数,但按重数计有三个素因子。

偶半素数恰好是形如 2p2p 的数,其中 pp 为素数。每个奇半素数都是两个奇素数的乘积。半素数有无穷多个,因为素数有无穷多个,而每个素数 pp 都对应一个不同的半素数 2p2p。

欧拉函数统计不超过 nn 且与 nn 互素的正整数的个数。对于两个不同素数的乘积,有

φ(pq)=(p−1)(q−1)(p≠q),\varphi(pq)=(p-1)(q-1)\qquad(p\ne q),

而对于素数的平方,则有

φ(p2)=p(p−1).\varphi(p^2)=p(p-1).

这一区别至关重要:适用于两个不同素因子的公式不能用于素数的平方。

计数与分布

设 S(x)S(x) 表示不超过 xx 的半素数的个数,π(x)\pi(x) 表示不超过 xx 的素数的个数,并用 pip_i 表示第 ii 个素数。一个精确的计数公式为

S(x)=∑i=1π(x)[π ⁣(xpi)−i+1].S(x)= \sum_{i=1}^{\pi(\sqrt{x})} \left[ \pi\!\left(\frac{x}{p_i}\right)-i+1 \right].

为推导这一公式,将每个半素数唯一地写成 pipjp_i p_j,其中 i≤ji\le j。它的较小素因子不超过 x\sqrt{x};固定 pip_i 后,可选的较大素因子满足

pi≤pj≤xpi.p_i\le p_j\le \frac{x}{p_i}.

求和式中的每一项统计的就是这些选择的个数,其中包括 pj=pip_j=p_i 的情形。

一个经典的渐近结果,即朗道关于殆素数的定理在 k=2k=2 时的情形,指出

S(x)∼xlog⁡log⁡xlog⁡x(x→∞),S(x)\sim\frac{x\log\log x}{\log x} \qquad(x\to\infty),

其中 log⁡\log 表示自然对数,∼\sim 表示两边的比值趋于 11。

因此,半素数的自然密度为零:

lim⁡x→∞S(x)x=0.\lim_{x\to\infty}\frac{S(x)}{x}=0.

不过,与素数定理比较可得

S(x)π(x)∼log⁡log⁡x.\frac{S(x)}{\pi(x)}\sim\log\log x.

所以,随着上界增大,半素数的累计个数与素数个数之比最终会超过任意给定的界限。

素数的平方对 S(x)S(x) 的贡献仅为 π(x)\pi(\sqrt{x}),其所占比例在渐近意义下可以忽略。因此,在这种计数意义下,几乎所有半素数都具有两个不同的素因子。

判定与因数分解

如果已知一个整数的完整素因数分解,就能立即判定它是否为半素数:各素因子指数之和必须等于二。反过来,若给出了分解式 n=pqn=pq,只要两个因子都通过素性检验,便可确认 nn 是半素数。

一种直接的判定方法是试除不超过 n\sqrt n 的所有可能的素因子。若最小素因子为 pp,则 nn 是半素数当且仅当 n/pn/p 是素数。这种方法对小整数很实用,但若以输入整数的位数衡量效率,则对大整数而言效率很低。

在整数分解中,两个素因子大小相近的大半素数尤其重要。含有较小因子的半素数通常可以很快分解;因此,仅凭一个数是半素数,并不能推断其分解具有多大的计算难度。

在密码学中的作用

在标准的双素数 RSA密码系统中,公开的模数为

n=pq,n=pq,

其中 pp 和 qq 是两个不同的大素数。这两个因子需要保密,而加密和签名运算则使用以 nn 为模的模算术。

知道 pp 和 qq 就能计算 φ(n)\varphi(n),进而在通常的 RSA 条件下,根据公钥指数求出私钥指数。对于由两个不同素数相乘得到的半素数,知道 φ(n)\varphi(n) 也能求出这两个因子,因为

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

这两个素数就是下列二次方程的根:

t2−(n−φ(n)+1)t+n=0.t^2-\bigl(n-\varphi(n)+1\bigr)t+n=0.

因此,分解模数便能破解标准 RSA。然而,一般的 RSA 求逆问题尚未被证明与因数分解等价。安全性还取决于密钥生成、填充方式和具体实现,而不只是模数是否为半素数。