In mathematics, a semiprime (also called biprime or 2-almost prime, or pq number) is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... (sequence A001358 in OEIS). Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... In mathematics, a natural number n is called k_almost prime iff Ω(n) = k, where Ω(n) is the sum of the exponents in the prime decomposition of n: A natural number is thus prime iff it is 1-almost prime, and semiprime iff it is 2-almost prime. ... In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

Currently, the largest known semiprime is (2^30,402,457 − 1)², which has over 18 million digits. This is the square of the largest known prime number; the square of any prime number is semiprime, so the largest known semiprime will always be the square of the largest known prime, unless the factors of the semiprime are not known. In algebra, the square of x is written x2 and is defined as the product of x with itself: x × x. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

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 pseudo-random number generators such as Blum Blum Shub. These methods rely on the fact that finding two large primes and multiplying them together is computationally simple, whereas finding the original factors appears to be difficult. In the RSA Factoring Challenge, RSA Security offers to award prizes up to $200,000 for the factoring of specific large semiprimes. The German Lorenz cipher machine, used in World War II for encryption of high-level messages. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically. ... In cryptography, RSA is an algorithm for public-key encryption. ... A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... The RSA Factoring Challenge is a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. ... RSA Security (NASDAQ: RSAS) is a public company. ...

In practical cryptography, it is not sufficient to choose just any semiprime; a good number must evade a number of well-known special-purpose algorithms that can factor numbers of certain form. The factors p and q of n should be very large, around the same order of magnitude as the square root (in other words, n is not a smooth number); this makes trial division and Pollard's rho algorithm impractical. At the same time they cannot be too close together, or else another simple test can factor the number. The number may also be chosen so that none of p − 1, p + 1, q − 1, or q + 1 are smooth numbers, protecting against Pollard's p-1 algorithm or Williams' p plus 1 algorithm. These checks cannot take future algorithms or secret algorithms into account however, introducing the possibility that numbers in use today may be broken by special-purpose algorithms. In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In number theory, a positive integer m is called B-smooth if all prime factors pi of m are such that pi ≤ B. For example 22335654 is 5-smooth since no prime factors are greater than 5. ... Trial division is the simplest and easiest to understand of the integer factorization algorithms. ... Pollards rho algorithm is a special-purpose integer factorization algorithm. ... In number theory, a positive integer m is called B-smooth if all prime factors of m are such that . For example, 22335654 is 5-smooth since none of its prime factors are greater than 5. ... Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ... In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm invented by H. C. Williams. ...

The value of Euler's totient function for a semiprime n = pq is particularly simple when p and q are distinct: The first thousand values of φ(n) In number theory, the totient (n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...

φ(n) = n + 1 − (p + q)

External links

• MathWorld: Semiprime