Safe prime
Encyclopedia
A safe prime is a prime number
of the form 2p + 1, where p is also a prime. (Conversely, the prime p is a Sophie Germain prime
.) The first few safe primes are
5, 7, 11
, 23
, 47
, 59
, 83
, 107
, 167
, 179
, 227
, 263
, 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 6k − 1 or, equivalently, q ≡ 5 (mod
6) — as is p > 3 (c.f. Sophie Germain prime
, second paragraph). Similarly, with the exception of 5, a safe prime q is of the form 4k − 1 or, equivalently, q ≡ 3 (mod 4) — trivially true since (q − 1) / 2 must evaluate to an odd natural number
. Combining both forms using lcm
(6,4) we determine that a safe prime q > 7 also must be of the form 12k−1 or, equivalently, q ≡ 11 (mod 12).
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 = 2p + 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 factoring
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 rho
+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 logarithm
-based techniques like Diffie-Hellman key exchange
. If 2p + 1 is a safe prime, the multiplicative group
of numbers modulo
2p + 1 has a subgroup of large prime order
. 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 congruences
can be used to generate pseudo-random numbers of use in Monte Carlo simulation.
s. However, Pocklington's criterion
can be used to prove the primality of 2p+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 = 2n + 1, it follows that (F − 1)/2 is a power of two
.
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 6k − 1. Mersenne primes are of the form 2m − 1, but 2m − 1 = 6k − 1 would imply that 2m is divisible by 6, which is impossible.
Just as every term except the last one of a Cunningham chain
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 10n + 7, are the last terms in such chains when they occur, since 2(10n + 7) + 1 = 20n + 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.
On 5 Feb 2007, a discrete logarithm modulo a 160-digit (530-bit) safe prime was computed. See Discrete logarithm records
.
Prime number
A 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 2p + 1, where p is also a prime. (Conversely, the prime p is a Sophie Germain prime
Sophie Germain prime
In 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, 11
11 (number)
11 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...
, 23
23 (number)
23 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...
, 47
47 (number)
47 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...
, 59
59 (number)
59 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...
, 83
83 (number)
83 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 ....
, 107
107 (number)
107 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....
, 167
167 (number)
167 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...
, 179
179 (number)
179 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...
, 227
227 (number)
227 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...
, 263
263 (number)
263 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 6k − 1 or, equivalently, q ≡ 5 (mod
Modulo operation
In 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 prime
Sophie Germain prime
In 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 4k − 1 or, equivalently, q ≡ 3 (mod 4) — trivially true since (q − 1) / 2 must evaluate to an odd natural number
Natural number
In 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 lcm
Least common multiple
In 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 12k−1 or, equivalently, q ≡ 11 (mod 12).
Applications
These primes are called "safe" because of their relationship to strong primeStrong prime
In 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 = 2p + 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 factoring
Integer factorization
In 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 rho
Pollard's rho algorithm
Pollard'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 logarithm
Discrete logarithm
In 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 exchange
Diffie-Hellman key exchange
Diffie–Hellman key exchange Synonyms of Diffie–Hellman key exchange include:*Diffie–Hellman key agreement*Diffie–Hellman key establishment*Diffie–Hellman key negotiation...
. If 2p + 1 is a safe prime, the multiplicative group
Group (mathematics)
In 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 modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
2p + 1 has a subgroup of large prime order
Order (group theory)
In 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 congruences
Sophie Germain prime
In 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 primeMersenne prime
In 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 criterion
Pocklington primality test
In 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 2p+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 = 2n + 1, it follows that (F − 1)/2 is a power of two
Power of two
In 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 6k − 1. Mersenne primes are of the form 2m − 1, but 2m − 1 = 6k − 1 would imply that 2m is divisible by 6, which is impossible.
Just as every term except the last one of a Cunningham chain
Cunningham chain
In 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 10n + 7, are the last terms in such chains when they occur, since 2(10n + 7) + 1 = 20n + 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·2265441−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 records
Discrete logarithm records
Discrete 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...
.