In number theory, a semiprime is a natural number that can be expressed as the product of two prime numbers. The two prime factors may be the same, in which case the semiprime is a perfect square of a prime. Semiprimes are sometimes called 2-almost primes or biprimes and form one of the simplest classes of composite numbers.
Definition and examples
Formally, n is semiprime if n = p*q where p and q are primes (not necessarily distinct). Small examples include 4 = 2×2, 6 = 2×3, 9 = 3×3, 10 = 2×5, 14 = 2×7 and 15 = 3×5. Because there are infinitely many primes, there are infinitely many semiprimes; for instance every number of the form 2p with p prime is a semiprime.
Elementary properties
Semiprimes have a narrow divisor structure. If n = p^2 is the square of a prime it has exactly three positive divisors: 1, p and n. If n = p*q with p ≠ q it has exactly four positive divisors: 1, p, q and n. In terms of prime-factor counts, semiprimes are precisely the integers for which the total number of prime factors counted with multiplicity equals two (often denoted Ω(n)=2).
History and role in cryptography
The arithmetic of semiprimes has long been studied in analytic and multiplicative number theory. In modern computer science they are important because many public-key cryptosystems rely on the practical difficulty of factoring large semiprimes. The RSA cryptosystem, for example, uses a modulus formed by the product of two large primes; the security assumption is that recovering the two prime factors from that product is computationally hard. See also general discussions of cryptography for context.
Special classes and distinctions
Certain subclasses of semiprimes are singled out for cryptographic or theoretical reasons. For example, a Blum integer is a semiprime p*q with p and q distinct primes both congruent to 3 mod 4; such numbers have special algebraic properties used in some protocols. It is also useful to distinguish semiprimes from primes (which have exactly two divisors) and from higher k-almost primes (which have more than two prime factors).
Computation and factorization
Determining whether a given large integer is semiprime requires either finding its prime factors or proving it has more or fewer than two prime factors. Simple methods include trial division and wheel sieves; more advanced factorization algorithms are used on large instances. The study of semiprimes connects elementary divisor facts with deeper questions about distribution and algorithmic complexity in number theory. For background reading see resources in number theory and introductory material on prime factorization such as basic integer arithmetic or general multiplicative structure. Additional references and overviews are available through standard texts and online introductions to primes and factoring theory.