semiprimea

A semiprime is a natural number that is the product of exactly two prime numbers, counted with multiplicity. Equivalently, a semiprime has a prime factorization consisting of two prime factors, possibly equal. Every semiprime is composite, but not every composite is semiprime.

There are two basic cases. If the two primes are distinct, n = p q with p ≠ q; such numbers are sometimes called squarefree semiprimes. If the primes are equal, n = p^2 is the square of a prime. Examples of distinct-prime semiprimes include 6, 10, 14, and 15; examples of squares of primes include 4, 9, and 25.

Divisors and factor structure follow directly from the prime factors. A semiprime with distinct primes has exactly four divisors: 1, p, q, and pq. A square of a prime has three divisors: 1, p, and p^2. The set of semiprimes up to x can be enumerated by all pairs of primes p ≤ q with pq ≤ x. The counting function S(x), the number of semiprimes ≤ x, satisfies S(x) ~ x log log x / log x as x grows large.

In computing and cryptography, semiprimes are notable because the product of two large primes is hard to factor. RSA moduli are typical examples of large semiprimes, and the difficulty of factoring such numbers underpins the security of RSA. Related concepts include biprimes and the broader study of numbers with a fixed total number of prime factors.

See also: biprime, prime factorization, RSA.