跳至內容

布盧姆數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數學中,如果某自然數n = p × q半素數,其中pq是兩個不同的素數,且等於3 mod 4,則n布盧姆數[1]也就是說,對於某個整數tpq必須等於4t + 3。這類整數稱作布盧姆素數。[2]因此,布盧姆數的因子是沒有虛部的高斯素數。前幾個布盧姆數為

21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 3,41, 381, 3 413, 417, 437, 453, 469, 473, 489, 497, ...(OEIS數列A016105

布盧姆數取名自電腦科學家曼紐爾·布盧姆[來源請求]

性質

給定某布盧姆數n = p × qQn是模n的所有二次剩餘,且與naQn互質。因此:[2]

  • a有四個模n的平方根,其中正好一個也在Qn中。
  • Qna的唯一平方根稱為an的主平方根。
  • 函數f : QnQn,其中f(x)被定義為f(x) = x2 mod n,是一個置換。f的反函數為:f−1(x) = x((p−1)(q−1)+4)/8 mod n[3]
  • 對於每個布盧姆整數n,-1的雅可比符號 mod n為+1,儘管-1不是n的二次餘數:

參考文獻

  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.