HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a semiprime is a natural number that is the product of exactly two
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
s. 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.


Examples and variations

The semiprimes less than 100 are: Semiprimes that are not square numbers are called discrete, distinct, or squarefree semiprimes: 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). These are:


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_^ pi(n/p_k) - k + 1 /math> where \pi(x) is the
prime-counting function In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number ''x''. It is denoted by (''x'') (unrelated to the number ). History Of great interest in number theory is t ...
and p_k denotes the ''k''th prime.


Properties

Semiprime numbers have no
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
s as factors other than themselves. 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\ne q) the value of
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
\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 RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
. For a square semiprime n=p^2, the formula is again simple: \varphi(n)=p(p-1)=n-p.


Applications

Semiprimes are highly useful in the area of
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
and number theory, most notably in public key cryptography, where they are used by
RSA RSA may refer to: Organizations Academia and education * Rabbinical Seminary of America, a yeshiva in New York City *Regional Science Association International (formerly the Regional Science Association), a US-based learned society *Renaissance S ...
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. In 1974 the Arecibo message was sent with a radio signal aimed at a
star cluster Star clusters are large groups of stars. Two main types of star clusters can be distinguished: globular clusters are tight groups of ten thousand to millions of old stars which are gravitationally bound, while open clusters are more loosely clust ...
. 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).


See also

* Chen's theorem


References


External links

* {{Classes of natural numbers Integer sequences Prime numbers Theory of cryptography