TOPICS
Search

Semiprime


A semiprime, also called a 2-almost prime, biprime (Conway et al. 2008), or pq-number, is a composite number that is the product of two (possibly equal) primes. The first few are 4, 6, 9, 10, 14, 15, 21, 22, ... (OEIS A001358). The first few semiprimes whose factors are distinct (i.e., the squarefree semiprimes) are 6, 10, 14, 15, 21, 22, 26, 33, 34, ... (OEIS A006881).

The square of any prime number is by definition a semiprime. The largest known semiprime is therefore the square of the largest known prime.

A formula for the number of semiprimes less than or equal to n is given by

 pi^((2))(x)=sum_(k=1)^(pi(sqrt(x)))[pi(x/(p_k))-k+1],
(1)

where pi(x) is the prime counting function and p_k is the kth prime (R. G. Wilson V, pers. comm., Feb. 7, 2006; discovered independently by E. Noel and G. Panos around Jan. 2005, pers. comm., Jun. 13, 2006).

The numbers of semiprimes less than 10^n for n=1, 2, ... are 3, 34, 299, 2625, 23378, 210035, ... (OEIS A066265).

For n=pq with p and q distinct, the following congruence is satisfied:

 p^q=p (mod n).
(2)

In addition, the totient function satisfies the simple identity

 phi(n)=(p-1)(q-1).
(3)

Generating provable semiprimes of more than 250 digits by methods other than multiplying two primes together is nontrivial. One method is factorization. From the Cunningham project, (6^(353)-1)/5 and 2^(997)-1 are factored semiprimes with 274 and 301 digits. Simiarly, the indices of Mersenne numbers that give semiprimes are 4, 9, 11, 23, 37, 41, 49, 59, 67, 83, ... (OEIS A085724). As of 2022, the largest known indices giving semiprimes are 1427 and 1487.

In 2005, Don Reble showed how an elliptic pseudo-curve and the Goldwasser-Kilian ECPP theorem could generate a 1084-digit provable semiprime without a known factorization (Reble 2005). Vitto (2021) subsequently found a backdoor strategy, factored Reble's 1084-digit semiprime, and introduced a new method for creating a semiprime certificate that is at least as secure as for random semiprimes of same size.

Encryption algorithms such as RSA encryption rely on special large numbers that have as their factors two large primes. The following tables lists some special semiprimes that are the product of two large (distinct) primes.

n=pqdigits in ndigits in pdigits in q
38!+1452323
10^(48)+19492128
10^(50)+27512229
10^(54)-3542332
10^(53)+63542529
10^(55)-9552531
10^(63)+19643232
RSA-1291296465
RSA-1401407070
RSA-1551557878

See also

Almost Prime, Chen's Theorem, Composite Number, Emirpimes, Greatest Prime Factor, Highly Composite Number, Jevons' Number, Landau's Problems, Large Number, Prime Factor, Prime Factorization, Prime Number, Rough Number, Round Number, RSA Encryption, RSA Number, Smooth Number, Sphenic Number

Explore with Wolfram|Alpha

References

Conway, J. H.; Dietrich, H.; O'Brien, E. A. "Counting Groups: Gnus, Moas, and Other Exotica." Math. Intell. 30, 6-18, 2008.Goldston, D. A.; Graham, S. W.; Pintz, J. and Yildirim, Y. "Small Gaps Between Primes or Almost Primes." 3 Jun 2005. http://arxiv.org/abs/math.NT/0506067.Reble, D. "Interesting Semiprimes." http://www.graysage.com/djr/isp.txt.Sloane, N. J. A. Sequences A001358/M3274, A0068814082, A066265, and A085724 in "The On-Line Encyclopedia of Integer Sequences."Vitto, G. "Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes." Cryptology ePrint Archive Paper 2021/1610, 2021. https://eprint.iacr.org/2021/1610.

Referenced on Wolfram|Alpha

Semiprime

Cite this as:

Weisstein, Eric W. "Semiprime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Semiprime.html

Subject classifications