布卢姆数

在数学中，如果某自然数n = p × q是半素数，其中p和q是两个不同的素数，且等于3 mod 4，则n是布卢姆数。也就是说，对于某个整数t，p和q必须等于4t + 3。这类整数称作布卢姆素数。因此，布卢姆数的因子是没有虚部的高斯素数。前几个布卢姆数为

21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 3,41, 381, 3 413, 417, 437, 453, 469, 473, 489, 497, ...（OEIS數列A016105）

布卢姆数取名自计算机科学家曼纽尔·布卢姆。

性质

给定某布卢姆数n = p × q，Q_n是模n的所有二次剩余，且与n和a ∈ Q_n互质。因此：

• a有四个模n的平方根，其中正好一个也在Q_n中。
• Q_n中a的唯一平方根称为a模n的主平方根。
• 函数f : Q_n → Q_n，其中f(x)被定义为f(x) = x² mod n，是一个置换。f的反函数为：f⁻¹(x) = x^{((p−1)(q−1)+4)/8} mod n。
• 对于每个布卢姆整数n，-1的雅可比符号 mod n为+1，尽管-1不是n的二次余数：

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