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 are21, 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, ...
Properties
Given a Blum integer,
Qn the set of all
quadratic residues modulo
n and coprime to
n and . Then: • For every Blum integer
n, −1 has a
Jacobi symbol mod
n of +1, although −1 is not a quadratic residue of
n: :: \left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1)^2=1 No Blum integer is the
sum of two squares. ==History==
History
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==