布盧姆整數

在數學上，如果一個自然數 n = p × q ，即一個半質數，其中 p 和 q 是相異的質數，且模 4 之值皆為 3 ^[1] 。也就是說 p 、q 皆為 4t + 3 的形式（t 是某個整數）。則 n 是一個「布盧姆整數」。^[2]而此時前述的 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。則：^[2]

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

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

歷史

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

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

參考資料

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.