布盧姆整數

在數學上，如果一個自然數 n = p × q ，即一個半質數，其中 p 和 q 是相異的質數，且模 4 之值皆為 3 。也就是說 p 、q 皆為 4t + 3 的形式（t 是某個整數）。則 n 是一個「布盧姆整數」。而此時前述的 p、q 稱為「布盧姆質數」。 這也就表示，布盧姆整數的因數是沒有虛數項的高斯質數。

前幾個布盧姆整數如下：

21 ， 33 ， 57 ， 69 ， 77 ， 93 ， 129 ， 133 ， 141 ， 161 ， 177 ，201，209，213，217，237，249，253，301，309，321，329，341，381，393， （OEIS數列A016105）

這些整數以電腦科學家曼紐爾﹒布盧姆之名命名。

性質

給定一個布盧姆整數 n = p × q 、Q_n 為所有模 n 下的二次剩餘並與 n 互質之數的集合，以及一數 a ∈ Q_n。則：

• 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)。
• 對於每個布盧姆整數 n ，-1 模 n 下的雅可比符號為 +1，儘管 -1 不是 n 的一個二次剩餘：

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

歷史

在現代質因數分解演算法，如 MPQS 和 NFS ，發展出來前，人們認為在選擇作為 RSA 的模數時，布盧姆整數很有用。

現今已不再認為此為合理的措施。因為 MPQS 以及 NFS 能夠像，隨機選擇質數去構造出來的 RSA 模數一樣容易地去分解布盧姆整數。