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

前幾個布盧姆整數如下:

213357697793129133141161177 ,201,209,213,217,237,249,253,301,309,321,329,341,381,393, (OEIS數列A016105

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

性質

編輯

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

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

歷史

編輯

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

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

參考資料

編輯
  1. ^ Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf頁面存檔備份,存於網際網路檔案館
  2. ^ 2.0 2.1 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.