布卢姆整数

在数学上，如果一个自然数 n = p × q ，即一个半质数，其中 p 和 q 是相异的质数，且模 4 之值皆为 3 。也就是说 p 、q 皆为 4t + 3 的形式（t 是某个整数）。则 n 是一个“布卢姆整数”。而此时前述的 p、q 称为“布卢姆质数”。 这也就表示，布卢姆整数的因数是没有虚数项的高斯质数。

前几个布卢姆整数如下：

21 ， 33 ， 57 ， 69 ， 77 ， 93 ， 129 ， 133 ， 141 ， 161 ， 177 ，201，209，213，217，237，249，253，301，309，321，329，341，381，393， （OEIS数列A016105）

这些整数以计算机科学家曼纽尔﹒布卢姆之名命名。

性质

给定一个布卢姆整数 n = p × q 、Q_n 为所有模 n 下的二次剩余并与 n 互质之数的集合，以及一数 a ∈ Q_n。则：

• a 有四个模 n 下的平方根，其中恰好一个在Q_n 里 。
• 这个属于Q_n 的唯一一个平方根，称为 a 的模 n 下的一个“主平方根”。
• 一函数 f： Q_n → Q_n ，定义为f (x) = x² (模n)。 f 的反函数为：f ^-1 (x) = x^{(p-1)(q-1) + 4 ) / 8} (模 n)。
• 对于每个布卢姆整数 n ，-1 模 n 下的雅可比符号为 +1，尽管 -1 不是 n 的一个二次剩余：

$\left({\frac {-1}{n}}\right)=\left({\frac {-1}{p}}\right)\left({\frac {-1}{q}}\right)=(-1)^{2}=1$

历史

在现代质因数分解算法，如 MPQS 和 NFS ，发展出来前，人们认为在选择作为 RSA 的模数时，布卢姆整数很有用。

现今已不再认为此为合理的措施。因为 MPQS 以及 NFS 能够像，随机选择质数去构造出来的 RSA 模数一样容易地去分解布卢姆整数。