safe prime

TheInfoList

OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative intege ...
, a
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 wa ...
''p'' is a Sophie Germain prime if 2''p'' + 1 is also prime. The number 2''p'' + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of
Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive number, positive integers , , and satisfy the equation for any integer value of greater than 2. The cases ...
. One attempt by Germain to prove Fermat’s Last Theorem was to let ''p'' be a prime number of the form 8''k'' + 7 and to let ''n'' = ''p'' – 1. In this case, $x^n + y^n = z^n$ is unsolvable. Germain’s proof, however, remained unfinished. Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if ''p'' is an odd prime and 2''p'' + 1 is also prime, then ''p'' must divide ''x'', ''y'', or ''z.'' Otherwise, $x^n + y^n \neq z^n$. This case where ''p'' does not divide ''x'', ''y'', or ''z'' is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time. Latter work by Kummer and others always divided the problem into first and second cases. Sophie Germain primes and safe primes have applications in
public key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
and primality testing. It has been
conjecture In mathematics, a conjecture is a Consequent, conclusion or a proposition that is proffered on a tentative basis without Formal proof, proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conje ...
d that there are
infinitely Infinity is that which is boundless, endless, or larger than any natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''th ...
many Sophie Germain primes, but this remains unproven.

# Individual numbers

The first few Sophie Germain primes (those less than 1000) are :2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ... Hence, 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, ... In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of ...
much larger Sophie Germain primes like 1,846,389,521,368 + 11600 are required. Two distributed computing projects,
PrimeGrid PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) 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 natura ...
and Twin Prime Search, include searches for large Sophie Germain primes. Some of the largest known Sophie Germain primes are given in the following table. On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a
discrete logarithm 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 mo ...
modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240) using a number field sieve algorithm; see Discrete logarithm records.

# Properties

There is no special primality test for safe primes the way there is for
Fermat prime 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 m ...
s and
Mersenne prime 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 mo ...
s. However, Pocklington's criterion can be used to prove the primality of 2''p'' + 1 once one has proven the primality of ''p''. Just as every term except the last one of a
Cunningham chain In mathematics, a Cunningham chain is a certain integer sequence, sequence of prime numbers. Cunningham chains are named after mathematician Allan Joseph Champneys Cunningham, A. J. C. Cunningham. They are also called chains of nearly doubled prime ...
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 In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
by 5. If a safe prime ''q'' is congruent to 7 modulo 8, then it is a divisor of the
Mersenne number In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minims (religious order), Minim friar, who studi ...
with its matching Sophie Germain prime as exponent. If ''q'' > 7 is a safe prime, then ''q'' divides 3(''q''−1)/2 − 1. (This follows from the fact that 3 is a
quadratic residue In number theory, an integer ''q'' is called a quadratic residue modulo operation, modulo ''n'' if it is Congruence relation, congruent to a Square number, perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv ...
mod ''q''.)

## Modular restrictions

With the exception of 7, a safe prime ''q'' is of the form 6''k'' − 1 or, equivalently, ''q'' ≡ 5 ( mod 6) – as is ''p'' > 3. 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 number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
. Combining both forms using lcm(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). It follows that 3 (also 12) is a
quadratic residue In number theory, an integer ''q'' is called a quadratic residue modulo operation, modulo ''n'' if it is Congruence relation, congruent to a Square number, perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv ...
mod ''q'' for any safe prime ''q'' > 7. (Thus, 12 is not a primitive root of any safe prime ''q'' > 7, and the only safe primes that are also
full reptend prime In number theory, a full reptend prime, full repetend prime, proper primeDickson, Leonard E., 1952, ''History of the Theory of Numbers, Volume 1'', Chelsea Public. Co. or long prime in Radix, base ''b'' is an parity (mathematics), odd prime number ...
s in
base 12 The duodecimal system (also known as base 12, dozenal, or, rarely, uncial) is a positional notation numeral system using 12 (number), twelve as its radix, base. The number twelve (that is, the number written as "12" in the decimal numerical syste ...
are 5 and 7.) If ''p'' is a Sophie Germain prime greater than 3, then ''p'' must be congruent to 2 mod 3. For, if not, it would be congruent to 1 mod 3 and 2''p'' + 1 would be congruent to 3 mod 3, impossible for a prime number. Similar restrictions hold for larger prime moduli, and are the basis for the choice of the "correction factor" 2''C'' in the Hardy–Littlewood estimate on the density of the Sophie Germain primes. If a Sophie Germain prime ''p'' is congruent to 3 (mod 4) (, ''Lucasian primes''), then its matching safe prime 2''p'' + 1 will be a divisor of the
Mersenne number In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minims (religious order), Minim friar, who studi ...
2''p'' − 1. Historically, this result of
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
was the first known criterion for a Mersenne number with a prime index to be composite. It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.

# Infinitude and density

It is
conjecture In mathematics, a conjecture is a Consequent, conclusion or a proposition that is proffered on a tentative basis without Formal proof, proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conje ...
d that there are infinitely many Sophie Germain primes, but this has not been proved.. Several other famous conjectures in number theory generalize this and the twin prime conjecture; they include the Dickson's conjecture, Schinzel's hypothesis H, and the Bateman–Horn conjecture. A
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be Mathematical optimisation, optimal, perfect, or Rationality, rational, but is nevertheless ...
estimate for the
number A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can ...
of Sophie Germain primes less than ''n'' is :$2C \frac \approx 1.32032\frac$ where :$C=\prod_ \frac\approx 0.660161$ is Hardy–Littlewood's twin prime constant. For ''n'' = 104, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190. For ''n'' = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032. The form of this estimate is due to G. H. Hardy and J. E. Littlewood, who applied a similar estimate to
twin prime A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin pr ...
s. A
sequence In mathematics, a sequence is an enumerated collection of mathematical object, objects in which repetitions are allowed and order theory, order matters. Like a Set (mathematics), set, it contains Element (mathematics), members (also called ''eleme ...
(''p'', 2''p'' + 1, 2(2''p'' + 1) + 1, ...) in which all of the numbers are prime is called a
Cunningham chain In mathematics, a Cunningham chain is a certain integer sequence, sequence of prime numbers. Cunningham chains are named after mathematician Allan Joseph Champneys Cunningham, A. J. C. Cunningham. They are also called chains of nearly doubled prime ...
of the first kind. Every term of such a sequence except the last is a Sophie Germain prime, and every term except the first is a safe prime. Extending the conjecture that there exist infinitely many Sophie Germain primes, it has also been conjectured that arbitrarily long Cunningham chains exist, although infinite chains are known to be impossible.

# Strong primes

A prime number ''q'' is a strong prime if and both have some large (around 500 digits) prime factors. For a safe prime , the number naturally has a large prime factor, namely ''p'', and so a 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 . This is true, for instance, of the ''p'' − 1 method.

# Applications

## Cryptography

Safe primes are also important in cryptography because of their use in
discrete logarithm 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 mo ...
-based techniques like
Diffie–Hellman key exchange Diffie–Hellman key exchangeSynonyms of Diffie–Hellman key exchange include: * Diffie–Hellman–Merkle key exchange * Diffie–Hellman key agreement * Diffie–Hellman key establishment * Diffie–Hellman key negotiation * Exponential key exc ...
. If is a safe prime, the multiplicative group of integers modulo has a
subgroup In group theory, a branch of mathematics, given a group (mathematics), group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ...
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''. A prime number ''p'' = 2''q'' + 1 is called a ''safe prime'' if ''q'' is prime. Thus, ''p'' = 2''q'' + 1 is a safe prime if and only if ''q'' is a Sophie Germain prime, so finding safe primes and finding Sophie Germain primes are equivalent in computational difficulty. The notion of a safe prime can be strengthened to a strong prime, for which both ''p'' − 1 and ''p'' + 1 have large prime factors. Safe and strong primes were useful as the factors of secret keys in the
RSA cryptosystem RSA (Rivest–Shamir–Adleman) is a public-key cryptography, 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 Leona ...
, because they prevent the system being broken by some
factorization 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 ...
algorithms such as Pollard's ''p'' − 1 algorithm. However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible. Similar issues apply in other cryptosystems as well, including
Diffie–Hellman key exchange Diffie–Hellman key exchangeSynonyms of Diffie–Hellman key exchange include: * Diffie–Hellman–Merkle key exchange * Diffie–Hellman key agreement * Diffie–Hellman key establishment * Diffie–Hellman key negotiation * Exponential key exc ...
and similar systems that depend on the security of the discrete log problem rather than on integer factorization. For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density. In Sophie Germain Counter Mode, it was proposed to use the arithmetic in the
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
of order equal to the Sophie Germain prime 2128 + 12451, to counter weaknesses in Galois/Counter Mode using the binary finite field GF(2128). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.

## Primality testing

In the first version of the
AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic algorithm, deterministic primality test, primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, ...
paper, a conjecture about Sophie Germain primes is used to lower the worst-case complexity from to . A later version of the paper is shown to have time complexity which can also be lowered to using the conjecture. Later variants of AKS have been proven to have complexity of without any conjectures or use of Sophie Germain primes.

## Pseudorandom number generation

Safe primes obeying certain congruences can be used to generate pseudo-random numbers of use in Monte Carlo simulation. Similarly, Sophie Germain primes may be used in the generation of pseudo-random numbers. The decimal expansion of 1/''q'' will produce a
stream A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a stream ...
of ''q'' − 1 pseudo-random digits, if ''q'' is the safe prime of a Sophie Germain prime ''p'', with ''p'' congruent to 3, 9, or 11 modulo 20. Thus "suitable" prime numbers ''q'' are 7, 23, 47, 59, 167, 179, etc. () (corresponding to ''p'' = 3, 11, 23, 29, 83, 89, etc.) (). The result is a stream of
length Length is a measure of distance. In the International System of Quantities, length is a quantity with Dimension (physical quantity), dimension distance. In most Measurement system, systems of measurement a Base unit (measurement), base unit f ...
''q'' − 1 digits (including leading zeros). So, for example, using ''q'' = 23 generates the pseudo-random digits 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Note that these digits are not appropriate for cryptographic purposes, as the value of each can be derived from its predecessor in the digit-stream.

# In popular culture

Sophie Germain primes are mentioned in the stage play '' Proof'' and the subsequent film.