Semiprime

In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Semiprimes are also called biprimes,^[1] since they include two primes, or second numbers,^[2] by analogy with how "prime" means "first".

Examples and variations

The semiprimes less than 100 are:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, and 95 (sequence A001358 in the OEIS)

Semiprimes that are not square numbers are called discrete, distinct, or squarefree semiprimes:

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (sequence A006881 in the OEIS)

The semiprimes are the case $k=2$ of the $k$ -almost primes, numbers with exactly $k$ 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:

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... (sequence A037143 in the OEIS)

Formula for number of semiprimes

A semiprime counting formula was discovered by E. Noel and G. Panos in 2005. Let $\pi _{2}(n)$ denote the number of semiprimes less than or equal to n. Then $\pi _{2}(n)=\sum _{k=1}^{\pi ({\sqrt {n}})}[\pi (n/p_{k})-k+1]$ where $\pi (x)$ is the prime-counting function and $p_{k}$ denotes the kth prime.^[4]

Properties

Semiprime numbers have no composite numbers as factors other than themselves.^[5] 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 $n=pq$ (with $p\neq q$ ) the value of Euler's totient function $\varphi (n)$ (the number of positive integers less than or equal to $n$ that are relatively prime to $n$ ) takes the simple form $\varphi (n)=(p-1)(q-1)=n-(p+q)+1.$ This calculation is an important part of the application of semiprimes in the RSA cryptosystem.^[6] For a square semiprime $n=p^{2}$ , the formula is again simple:^[6] $\varphi (n)=p(p-1)=n-p.$

Applications

Semiprimes are highly useful in the area of cryptography and number theory, most notably in public key cryptography, where they are used by RSA and pseudorandom number generators such as Blum Blum Shub. These methods rely on the fact that finding two large primes and multiplying them together (resulting in a semiprime) is computationally simple, whereas finding the original factors appears to be difficult. In the RSA 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.^[7]

In 1974 the Arecibo message was sent with a radio signal aimed at a star cluster. It consisted of $1679$ binary digits intended to be interpreted as a $23\times 73$ bitmap image. The number $1679=23\cdot 73$ 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).^[8]

References

^ Sloane, N. J. A. (ed.). "Sequence A001358". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Nowicki, Andrzej (2013-07-01), Second numbers in arithmetic progressions, arXiv:1306.6424
^ Stewart, Ian (2010). Professor Stewart's Cabinet of Mathematical Curiosities. Profile Books. p. 154. ISBN 9781847651280.
^ Ishmukhametov, Sh. T.; Sharifullina, F. F. (2014). "On distribution of semiprime numbers". Russian Mathematics. 58 (8): 43–48. doi:10.3103/S1066369X14080052. MR 3306238. S2CID 122410656.
^ French, John Homer (1889). Advanced Arithmetic for Secondary Schools. New York: Harper & Brothers. p. 53.
^ Jump up to: ^a ^b Cozzens, Margaret; Miller, Steven J. (2013). The Mathematics of Encryption: An Elementary Introduction. Mathematical World. Vol. 29. American Mathematical Society. p. 237. ISBN 9780821883211.
^ "The RSA Factoring Challenge is no longer active". RSA Laboratories. Archived from the original on 2013-07-27.
^ du Sautoy, Marcus (2011). The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. p. 19. ISBN 9780230120280.

External links

Weisstein, Eric W. "Semiprime". MathWorld.

[1] Sloane, N. J. A. (ed.). "Sequence A001358". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[2] Nowicki, Andrzej (2013-07-01), Second numbers in arithmetic progressions, arXiv:1306.6424

[3] Stewart, Ian (2010). Professor Stewart's Cabinet of Mathematical Curiosities. Profile Books. p. 154. ISBN 9781847651280.

[4] Ishmukhametov, Sh. T.; Sharifullina, F. F. (2014). "On distribution of semiprime numbers". Russian Mathematics. 58 (8): 43–48. doi:10.3103/S1066369X14080052. MR 3306238. S2CID 122410656.

[5] French, John Homer (1889). Advanced Arithmetic for Secondary Schools. New York: Harper & Brothers. p. 53.

[moe-6] Jump up to: ^a ^b Cozzens, Margaret; Miller, Steven J. (2013). The Mathematics of Encryption: An Elementary Introduction. Mathematical World. Vol. 29. American Mathematical Society. p. 237. ISBN 9780821883211.

[7] "The RSA Factoring Challenge is no longer active". RSA Laboratories. Archived from the original on 2013-07-27.

[8] u Sautoy, Marcus (2011). The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. p. 19. ISBN 9780230120280.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t e Divisibility-based sets of integers
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Descartes Refactorable Superperfect

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers