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.
Given n = p × q a Blum integer, Qn the set of all quadratic residues modulo n and coprime to n and a ∈ Qn. Then:
- 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
- ^ a b Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" Archived 2012-04-21 at the Wayback Machine. Summer course on cryptography, MIT, 1996-2001
- ^ "A016105 - OEIS". oeis.org. Retrieved 2022-10-03.
- ^ Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Handbook of applied cryptography. Boca Raton: CRC Press. p. 102. ISBN 0849385237. OCLC 35292671.