Semiprime

Formula for number of semiprimes

Let ${\displaystyle {\pi }_2(n)}$ denote the number of semiprimes less than or equal to n. Then $${\displaystyle {\pi }_2(n)=\sum _{k=1}^{\pi \left(\sqrt{n}\right)}\left[\pi \left(\frac{n}{p_k}\right)-k+1\right]}$$ where ${\displaystyle \pi (x)}$ is the prime-counting function and ${\displaystyle p_k}$ denotes the kth prime.

To see this, take ${\displaystyle p_k}$ to be the smaller prime factor. Then ${\displaystyle p_k\le \sqrt{n}}$, and the larger factor may be any prime ${\displaystyle q}$ satisfying ${\displaystyle p_k\le q\le n/p_k}$. The number of such primes is ${\displaystyle \pi (n/p_k)-\pi (p_k-1)}$. Since ${\displaystyle p_k}$ is the kth prime, ${\displaystyle \pi (p_k-1)=k-1}$, giving the summand ${\displaystyle \pi (n/p_k)-k+1}$.

Properties

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

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