A
safe prime is a
prime numberA prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
of the form 2
p + 1, where
p is also a prime. (Conversely, the prime
p is a
Sophie Germain primeIn number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number...
.) The first few safe primes are
5,
7,
1111 is the natural number following 10 and preceding 12.Eleven is the first number which cannot be counted with a human's eight fingers and two thumbs additively. In English, it is the smallest positive integer requiring three syllables and the largest prime number with a single-morpheme name...
,
2323 is the natural number following 22 and preceding 24.- In mathematics :Twenty-three is the ninth prime number, the smallest odd prime that is not a twin prime. Twenty-three is also the fifth factorial prime, the third Woodall prime...
,
4747 is the natural number following 46 and preceding 48.-In mathematics:Forty-seven is the fifteenth prime number, a safe prime, the thirteenth supersingular prime, and the sixth Lucas prime. Forty-seven is a highly cototient number...
,
5959 is the natural number following 58 and preceding 60.-In mathematics:Fifty-nine is the 17th smallest prime number. The next is sixty-one, with which it comprises a twin prime. 59 is an irregular prime, a safe prime and the 14th supersingular prime. It is an Eisenstein prime with no imaginary...
,
8383 is the natural number following 82 and preceding 84.-In mathematics:Eighty-three is the sum of three consecutive primes as well as the sum of five consecutive primes ....
,
107107 is the natural number following 106 and preceding 108.-In mathematics:One hundred [and] seven is the 28th prime number. The next prime is 109, with which it comprises a twin prime, making 107 a Chen prime....
,
167167 is the natural number following 166 and preceding 168.-In mathematics:* 167 is an odd number* 167 is a Chen prime, since the next odd number, 169, is a square of a prime...
,
179179 is the natural number following 178 and preceding 180.-In mathematics:* 179 is an odd number* 179 is a deficient number, as 1 is less than 179* 179 is a Gaussian number* 179 is an odious number* 179 is a square-free number...
,
227227 is the natural number between 226 and 228. It is also a prime number.-In mathematics:227 is a prime number, and a twin prime with 229 . 223 plus 4 is 227, so they are cousin primes...
,
263263 is the natural number between 262 and 264. It is also a prime number.-In mathematics:263 is an irregular prime, an Eisenstein prime, a long prime, a Chen prime, a Gaussian prime, a happy prime, a sexy prime, a safe prime, and a Higgs prime....
, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907.
With the exception of 7, a safe prime
q is of the form 6
k − 1 or, equivalently,
q ≡ 5 (
modIn computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
6) — as is
p > 3 (c.f.
Sophie Germain primeIn number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number...
, second paragraph). Similarly, with the exception of 5, a safe prime
q is of the form 4
k − 1 or, equivalently,
q ≡ 3 (mod 4) — trivially true since (
q − 1) / 2 must evaluate to an odd
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
. Combining both forms using
lcmIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
(6,4) we determine that a safe prime
q > 7 also must be of the form 12
k−1 or, equivalently,
q ≡ 11 (mod 12).
Applications
These primes are called "safe" because of their relationship to
strong primeIn mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory.- Definition in cryptography :...
s. A prime number
q is a
strong prime if
q + 1 and
q − 1 both have large prime factors. For a safe prime
q = 2
p + 1, the number
q − 1 naturally has a large prime factor, namely
p, and so safe prime
q meets part of the criteria for being a strong prime. The running times of some methods of
factoringIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
a number with
q as a prime factor depend partly on the size of the prime factors of
q − 1. This is true, for instance, of the
Pollard rhoPollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.-Core ideas:...
+1 and −1 methods. Although the most efficient known integer factorization methods do not depend on the size of the prime factors of
q−1, this is nonetheless considered important in cryptography: for instance, the ANSI X9.31 standard mandates that
strong primes (not
safe primes) be used for RSA moduli.
Safe primes are also important in cryptography because of their use in
discrete logarithmIn mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
-based techniques like
Diffie-Hellman key exchangeDiffie–Hellman key exchange Synonyms of Diffie–Hellman key exchange include:*Diffie–Hellman key agreement*Diffie–Hellman key establishment*Diffie–Hellman key negotiation...
. If 2
p + 1 is a safe prime, the multiplicative
groupIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
of numbers
moduloIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
2
p + 1 has a subgroup of large prime
orderIn group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....
. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to
p.
Safe primes obeying
certain congruencesIn number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number...
can be used to generate pseudo-random numbers of use in Monte Carlo simulation.
Further properties
There is no special primality test for safe primes the way there is for Fermat primes and
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
s. However,
Pocklington's criterionIn mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer to decide whether a given number N is prime...
can be used to prove the primality of 2
p+1 once one has proven the primality of
p.
With the exception of 5, there are no Fermat primes that are also safe primes. Since Fermat primes are of the form
F = 2
n + 1, it follows that (
F − 1)/2 is a
power of twoIn mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
.
With the exception of 7, there are no Mersenne primes that are also safe primes. This follows from the statement above that all safe primes except 7 are of the form 6
k − 1. Mersenne primes are of the form 2
m − 1, but 2
m − 1 = 6
k − 1 would imply that 2
m is divisible by 6, which is impossible.
Just as every term except the last one of a
Cunningham chainIn mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes....
of the first kind is a Sophie Germain prime, so every term except the first of such a chain is a safe prime. Safe primes ending in 7, that is, of the form 10
n + 7, are the last terms in such chains when they occur, since 2(10
n + 7) + 1 = 20
n + 15 is divisible by 5.
If a safe prime
q is congruent to 7 mod 8, then it is a divisor of the Mersenne number with its matching Sophie Germain prime as exponent.
Records
, the largest known safe prime is 183027·2
265441−1. This prime, along with the corresponding largest known Sophie Germain prime, was found by Tom Wu on March 22, 2010 using the programs sgsieve and LLR.
On 5 Feb 2007, a discrete logarithm modulo a 160-digit (530-bit) safe prime was computed. See
Discrete logarithm recordsDiscrete logarithm records are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation gx = h given elements g and h of a finite cyclic group G...
.