布盧姆數

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