布盧姆數

在數學中，如果某自然數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.