In mathematics, a natural number n is a Blum integer if n = p×q is a semiprime for which p and q are distinct prime numbers congruent to 3 mod 4. That is, p and q must be of the form 4t + 3, for some integer t. Integers of this form are referred to as Blum primes. This means that the factors of a Blum integer are Gaussian primes with no imaginary part. The first few Blum integers are
- 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, ... (sequence A016105 in the OEIS)
The integers were named for computer scientist Manuel Blum.
- a has four square roots modulo n, exactly one of which is also in Qn
- The unique square root of a in Qn is called the principal square root of a modulo n
- The function f: Qn → Qn defined by f(x) = x2 mod n is a permutation. The inverse function of f is: f −1(x) = x((p − 1)(q − 1) + 4)/8 mod n.
- For every Blum integer n, −1 has a Jacobi symbol mod n of +1, although −1 is not a quadratic residue of n:
Before modern factoring algorithms, such as MPQS and NFS, were developed, it was thought to be useful to select Blum integers as RSA moduli. This is no longer regarded as a useful precaution, since MPQS and NFS are able to factor Blum integers with the same ease as RSA moduli constructed from randomly selected primes.
- Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf
- Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
- Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Handbook of applied cryptography. Boca Raton: CRC Press. p. 102. ISBN 0849385237. OCLC 35292671.