跳转到内容

布卢姆数

本页使用了标题或全文手工转换
维基百科,自由的百科全书

数学中,如果某自然数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.