布盧姆整數

在數學上，如果一個自然數 n = p × q ，即一個半質數，其中 p 和 q 是相異的質數，且模 4 之值皆為 3 Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from https://www.gilith.com/research/talks/cambridge1997.pdf  。也就是說 p 、q 皆為 4t + 3 的形式（t 是某個整數）。則 n 是一個「布盧姆整數」。Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" . Summer course on cryptography, MIT, 1996-2001而此時前述的 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，      

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

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

 a 有四個模 n 下的平方根，其中恰好一個在Qn 裡 。 
 這個屬於Qn 的唯一一個平方根，稱為 a 的模 n 下的一個「主平方根」。 
 一函數  f： Qn → Qn ，定義為f (x) = x2 (模n)。 f 的反函數為：f -1 (x) = x(p-1)(q-1) + 4 ) / 8  (模 n)。
 對於每個布盧姆整數 n ，-1 模 n 下的雅可比符號為 +1，儘管 -1 不是 n 的一個二次剩餘： 



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

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

 參考資料 

Category:整数数列