Sophie Germain

Lore & Background

Sophie Germain primes are named after the French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. 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. 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, she proved a result now known as Sophie Germain's theorem, which states that if p is an odd prime and 2p + 1 is also prime, then p must divide x, y, or z. Otherwise, x^n + y^n ≠ 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. Later work by Kummer and others always divided the problem into first and second cases.

Reader's Guide

Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. Safe primes are 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 integers modulo 2p + 1 has a subgroup of large prime order. A prime number p = 2q + 1 is called a safe prime if q is prime. Thus, p = 2q + 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, because they prevent the system being broken by some factorization 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 and similar systems that depend on the security of the discrete logarithm problem rather than on integer factorization.

Did You Know?

• Sophie Germain primes are named after the French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem.
• It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.
• 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 prime RSA-240 + 49204 (the first safe prime above RSA-240).
• If a Sophie Germain prime p is congruent to 3 (mod 4), then its matching safe prime 2p + 1 (congruent to 7 modulo 8) will be a divisor of the Mersenne number 2^p − 1.
• 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.