布卢姆数

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

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互质。因此：^[2]

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

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

参考文献

1. Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf （页面存档备份，存于互联网档案馆）
2. Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" （页面存档备份，存于互联网档案馆）. Summer course on cryptography, MIT, 1996-2001
3. Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott. Handbook of applied cryptography. Boca Raton: CRC Press. 1997: 102. ISBN 0849385237. OCLC 35292671.