# Blum integer

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.^{[1]} That is, *p* and *q* must be of the form 4*t* + 3, for some integer *t*. Integers of this form are referred to as Blum primes.^{[2]} 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.

## Properties[edit]

Given *n* = *p*×*q* a Blum integer, *Q*_{n} the set of all quadratic residues modulo n and coprime to n and *a* ∈ *Q*_{n}. Then:^{[2]}

*a*has four square roots modulo*n*, exactly one of which is also in*Q*_{n}- The unique square root of
*a*in*Q*_{n}is called the*principal square root*of*a*modulo*n* - The function
*f:**Q*_{n}→*Q*_{n}defined by*f*(*x*) =*x*^{2}mod*n*is a permutation. The inverse function of*f*is:*f*^{−1}(*x*) =*x*^{((p − 1)(q − 1) + 4)/8}mod*n*.^{[3]} - For every Blum integer
*n*, −1 has a Jacobi symbol mod*n*of +1, although −1 is not a quadratic residue of*n*:

## History[edit]

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.

## References[edit]

**^**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". Summer course on cryptography, MIT, 1996-2001 **^**A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography ISBN 0-8493-8523-7.