Safe and Sophie Germain primes

[1] One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1.

Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time.

[4] On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm 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.

However, Pocklington's criterion can be used to prove the primality of 2p + 1 once one has proven the primality of p. 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.

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.

Historically, this result of Leonhard Euler was the first known criterion for a Mersenne number with a prime index to be composite.

For n = 104, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190.

Extending the conjecture that there exist infinitely many Sophie Germain primes, it has also been conjectured that arbitrarily long Cunningham chains exist,[21] although infinite chains are known to be impossible.

Safe primes are also important in cryptography because of their use in discrete logarithm-based techniques like Diffie–Hellman key exchange.

However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible.

[24] 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.

[25] In Sophie Germain Counter Mode, it was proposed to use the arithmetic in the finite field of order equal to the safe prime 2128 + 12451, to counter weaknesses in Galois/Counter Mode using the binary finite field GF(2128).

[26] In the first version of the AKS primality test paper, a conjecture about Sophie Germain primes is used to lower the worst-case complexity from O(log12n) to O(log6n).

[27] Later variants of AKS have been proven to have complexity of O(log6n) without any conjectures or use of Sophie Germain primes.

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.

[citation needed] Sophie Germain primes are mentioned in the stage play Proof[29] and the subsequent film.