布卢姆数
外观
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在数学中,如果某自然数n = p × q是半素数,其中p和q是两个不同的素数,且等于3 mod 4,则n是布卢姆数。[1]也就是说,对于某个整数t,p和q必须等于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 × 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.