数学上,如果一个自然数 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.