查看“︁布盧姆整數”︁的源代码

在[[数学|數學]]上，如果一個[[自然数|自然數]] n = p × q ，即一個[[半素数|半質數]]，其中 p 和 q 是相異的[[素数|質數]]，且[[模]] 4 之值皆為 3 <ref name = "HurdBlum">Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf {{Wayback|url=http://www.gilith.com/research/talks/cambridge1997.pdf |date=20160305160343 }}</ref> 。也就是說 p 、q 皆為 4t + 3 的形式（t 是某個整數）。則 n 是一個「'''布盧姆整數'''」。<ref name="GoldBell">[[莎菲·戈德瓦塞爾|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Wayback|url=http://cseweb.ucsd.edu/~mihir/papers/gb.html |date=20120421084751 }}. Summer course on cryptography, MIT, 1996-2001</ref>而此時前述的 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|id=A016105}}     

這些整數以電腦科學家[[曼纽尔·布卢姆|曼紐爾﹒布盧姆]]之名命名。 

== 性質 ==
給定一個布盧姆整數 ''n'' = ''p × q 、Q''<sub>''n''</sub> 為所有模 n 下的[[二次剩余|二次剩餘]]並與 n 互質之數的集合，以及一數 a ∈ Q<sub>''n''</sub>。則：<ref name="GoldBell"/>

* ''a'' 有四個模 ''n'' 下的平方根，其中恰好一個在''Q''<sub>''n''</sub> 裡 。 
* 這個屬於''Q''<sub>''n''</sub> 的唯一一個平方根，稱為 a 的模 ''n'' 下的一個「主平方根」。 
* 一函數  ''f：'' ''Q''<sub>''n''</sub> → ''Q''<sub>''n''</sub> ，定義為''f'' (''x'') = ''x''<sup>2</sup> (模''n'')。 ''f'' 的反函數為：''f'' <sup>-1</sup> (''x'') = ''x''<sup>(p-1)(q-1) + 4 ) / 8</sup>  (模 ''n'')。<ref>{{Cite book| title=Handbook of applied cryptography| url=https://archive.org/details/handbookappliedc00mene_146| last1=Menezes | first1 = Alfred |last2 =van Oorschot | first2 =Paul | last3 = Vanstone|first3=Scott| date=1997|publisher=CRC Press| isbn=0849385237| location=Boca Raton| oclc=35292671| page =[https://archive.org/details/handbookappliedc00mene_146/page/n102 102]}}</ref>
* 對於每個布盧姆整數 ''n'' ，-1 模 ''n'' 下的[[雅可比符号|雅可比符號]]為 +1，儘管 -1 不是 ''n'' 的一個二次剩餘： 

:: <math>\left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1)^2=1</math>

== 歷史 ==
在現代質因數分解演算法，如 [[二次篩選法|MPQS]] 和 [[普通数域筛选法|NFS]] ，發展出來前，人們認為在選擇作為 [[RSA加密演算法|RSA]] 的模數時，布盧姆整數很有用。  

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

== 參考資料 ==
{{Reflist}}
[[Category:整数数列]]