布卢姆整数

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

• 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)。^[3]
• 对于每个布卢姆整数 n ，-1 模 n 下的雅可比符号为 +1，尽管 -1 不是 n 的一个二次剩余：

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

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

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