Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Blum integer

Product of two distinct primes ≡ 3 (mod 4)

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated March 31, 2026

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. The largest known Blum integer is (282,589,933 - 1)(2136,279,841 - 1), a number with 65,886,368 digits.

01Properties

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

02History

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.

Watch videos about Blum integerExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Blum integer”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.