### What are they?

A *Sophie Germain* prime is a prime such that $2p+1$ is also prime - for example, 23 is a Sophie Germain prime since 47 is also prime.

The largest known Sophie Germain prime has close to 400,000 digits; it is conjectured that there are infinitely many such primes, although this has not yet been proved.

Relatedly, a *Cunningham chain* is a sequence of numbers such that $u_0$ is a Sophie Germain prime, and $u_{n+1} = 2u_n + 1$ if $u_n$ is a prime - for example, ${ 2, 5, 11, 23, 47, 95}$ is a Cunningham chain. Another unproved conjecture is that there are Cunningham chains of any length you like (although we know there aren’t infinitely long ones.)

### Why are they important?

Germain used primes of this form in her work on Fermat’s Last Theorem - she was the first to attack FLT with a grand plan rather than a piecemeal approach. Her particular idea embodies “Wrong, but useful”: it didn’t *work*, but it led to interesting things.

In modern times, Sophie Germain primes (and their related ‘safe primes’) are important cryptographically: the products of unsafe primes are vulnerable to various factorisation methods such as Pollard’s rho - and similar problems exist when looking at cryptographic systems based on the discrete logarithm problem.

Sophie Germain primes can also be used as a basic random number generator: the decimal expansion of $\frac{1}{q}$ produces a stream of $q-1$ pseudo-random digits if $q$ is the safe prime of a Sophie Germain prime $p$, such that $p$ is congruent to 3, 9 or 11 (modulo 20). (This is one of my favourite ways to generate ‘random’ numbers without a calculator.)

### Who was Germain?

Marie-Sophie Germain was born in Paris in 1776. Denied a career as a mathematician, she worked independently, corresponding with Gauss, Lagrange and Legendre, working under the pseudonym of Auguste Le Blanc until Lagrange requested a meeting with the young ‘man’ of unusual intelligence.

She died, also in Paris, in 1831.

## Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008.
He lives with an espresso pot and nothing to prove.