Inmathematics, asemiprime is anatural number that is theproduct of exactly twoprime numbers. The two primes in the product may equal each other, so the semiprimes include thesquares of prime numbers.Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Semiprimes are also calledbiprimes,[1] since they include two primes, orsecond numbers,[2] by analogy with how "prime" means "first".
The semiprimes are the case of the-almost primes, numbers with exactly prime factors. However some sources use "semiprime" to refer to a larger set of numbers, the numbers with at most two prime factors (including unit (1), primes, and semiprimes).[3] These are:
A semiprime counting formula was discovered by E. Noel and G. Panos in 2005.[4] Let denote the number of semiprimes less than or equal ton. Thenwhere is theprime-counting function and denotes thekth prime.[5]
Semiprime numbers have nocomposite numbers as factors other than themselves.[6] For example, the number 26 is semiprime and its only factors are 1, 2, 13, and 26, of which only 26 is composite.
For a squarefree semiprime (with)the value ofEuler's totient function (the number of positive integers less than or equal to that arerelatively prime to) takes the simple formThis calculation is an important part of the application of semiprimes in theRSA cryptosystem.[7]For a square semiprime, the formula is again simple:[7]
Semiprimes are highly useful in the area ofcryptography andnumber theory, most notably inpublic key cryptography, where they are used byRSA andpseudorandom number generators such asBlum Blum Shub. These methods rely on the fact that finding two large primes and multiplying them together (resulting in a semiprime) is computationally simple, whereasfinding the original factors appears to be difficult. In theRSA Factoring Challenge,RSA Security offered prizes for the factoring of specific large semiprimes and several prizes were awarded. The original RSA Factoring Challenge was issued in 1991, and was replaced in 2001 by the New RSA Factoring Challenge, which was later withdrawn in 2007.[8]
In 1974 theArecibo message was sent with a radio signal aimed at astar cluster. It consisted of binary digits intended to be interpreted as abitmap image. The number was chosen because it is a semiprime and therefore can be arranged into a rectangular image in only two distinct ways (23 rows and 73 columns, or 73 rows and 23 columns).[9]
