A semiprime is a positive integer that is the product of exactly two prime numbers, counted with multiplicity. Thus is semiprime if , where and are primes and may be equal. Semiprimes are studied in number theory and are important in cryptography, where products of two large primes provide the moduli used in systems such as RSA.
Definition and examples
The semiprimes, in increasing order, begin
For example:
- and are semiprimes because a repeated prime factor counts twice.
- and are semiprimes with two distinct prime factors.
- is not semiprime: it has three prime factors when multiplicity is counted.
- Neither nor any prime number is semiprime.
The fundamental theorem of arithmetic ensures that this definition is unambiguous. If
is the prime factorization of , define
Then is semiprime exactly when .
Semiprimes are therefore the special case of almost primes, integers having exactly prime factors counted with multiplicity. Some sieve-theoretic terminology instead concerns integers with at most prime factors, so the convention must be checked in that context.
Types and elementary properties
There are two types of semiprime:
| Type | Form | Example | Number of positive divisors |
|---|---|---|---|
| Prime square | 3 | ||
| Product of distinct primes | , | 4 |
A semiprime with distinct prime factors is a square-free integer. Its positive divisors are precisely . A prime square instead has the divisors .
Having four positive divisors does not by itself characterize semiprimes: also has exactly four divisors, but has three prime factors counted with multiplicity.
The only even semiprimes are numbers of the form , where is prime. Every odd semiprime is the product of two odd primes. There are infinitely many semiprimes, since there are infinitely many primes and each prime produces a distinct semiprime .
For Euler’s totient function, which counts the positive integers at most that are coprime to ,
whereas
The distinction is essential: the formula for two distinct prime factors does not apply to a prime square.
Counting and distribution
Let denote the number of semiprimes not exceeding , and let denote the number of primes not exceeding . Write for the -th prime. An exact counting formula is
To obtain this formula, write each semiprime uniquely as with . Its smaller prime factor is at most ; for a fixed , the permitted larger factors satisfy
The summand counts these choices, including .
A classical asymptotic result, the case of Landau’s theorem on almost primes, states that
where is the natural logarithm and means that the ratio of the two sides tends to .
Consequently, semiprimes have natural density zero:
Nevertheless, comparison with the prime number theorem gives
Thus the cumulative number of semiprimes eventually exceeds the number of primes by an unbounded factor.
Prime squares contribute only to , a negligible proportion asymptotically. Almost all semiprimes, in this counting sense, have distinct prime factors.
Recognition and factorization
Given a complete prime factorization of an integer, determining whether it is semiprime is immediate: the sum of the prime-factor exponents must equal two. Conversely, a proposed factorization certifies semiprimality once both factors have passed a primality test.
A straightforward recognition method tries possible prime divisors up to . If the smallest prime divisor is , then is semiprime exactly when is prime. This method is practical for small integers but inefficient for large inputs measured by their number of digits.
In integer factorization, large semiprimes whose factors have comparable sizes are particularly important. A semiprime with a small factor can often be factored quickly; the definition of semiprimality alone therefore implies no particular level of computational difficulty.
Role in cryptography
In the standard two-prime RSA cryptosystem, the public modulus is
where and are distinct large primes. The factors are kept secret, while encryption and signature operations use modular arithmetic modulo .
Knowing and allows computation of , and hence recovery of the private exponent from the public exponent under the usual RSA conditions. For a distinct-prime semiprime, knowing also reveals the factors, because
The primes are then the roots of the quadratic equation
Factoring the modulus therefore breaks standard RSA. However, the general problem of inverting RSA has not been proved equivalent to factoring. Security also depends on key generation, padding, and implementation, rather than on semiprimality alone.