布卢姆数
(重定向自布盧姆數)
在数学中,如果某自然数n = p × q是半素数,其中p和q是两个不同的素数,且等于3 mod 4,则n是布卢姆数。[1]也就是说,对于某个整数t,p和q必须等于4t + 3。这类整数称作布卢姆素数。[2]因此,布卢姆数的因子是没有虚部的高斯素数。前几个布卢姆数为
性质
编辑给定某布卢姆数n = p × q,Qn是模n的所有二次剩余,且与n和a ∈ Qn互质。因此:[2]
- a有四个模n的平方根,其中正好一个也在Qn中。
- Qn中a的唯一平方根称为a模n的主平方根。
- 函数f : Qn → Qn,其中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的二次余数:
参考文献
编辑- ^ Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf (页面存档备份,存于互联网档案馆)
- ^ 2.0 2.1 Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" (页面存档备份,存于互联网档案馆). Summer course on cryptography, MIT, 1996-2001
- ^ Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott. Handbook of applied cryptography. Boca Raton: CRC Press. 1997: 102. ISBN 0849385237. OCLC 35292671.