Inmathematics, anatural numbern is aBlum integer ifn =p ×q is asemiprime for whichp andq are distinctprime numbers congruent to 3mod 4.^[1] That is,p andq must be of the form4t + 3, for some integert. Integers of this form are referred to as Blum primes.^[2] This means that the factors of a Blum integer areGaussian 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, ... (sequenceA016105 in theOEIS)

The integers were named for computer scientistManuel Blum.^[3]

Givenn =p ×q a Blum integer,Q_n the set of allquadratic residues modulon and coprime ton anda ∈Q_n. Then:^[2]

• a has four square roots modulon, exactly one of which is also inQ_n
• The unique square root ofa inQ_n is called theprincipal square root ofa modulon
• The functionf :Q_n →Q_n defined byf(x) =x² modn is a permutation. The inverse function off is:f⁻¹(x) =x^{((p−1)(q−1)+4)/8} modn.^[4]
• For every Blum integern, −1 has aJacobi symbol modn of +1, although −1 is not a quadratic residue ofn:

${\displaystyle \left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1{)}^2=1}$

No Blum integer is thesum of two squares.

Before modern factoring algorithms, such asMPQS andNFS, were developed, it was thought to be useful to select Blum integers asRSA 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.^{[citation needed]}

• Integer sequences

• Webarchive template wayback links
• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from March 2021