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
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:
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.