MHB Why did Sophie Come Up with Germain Primes?

[matqkks]

Why did Germain come up with her Germain primes? I am intrigued to know why Sophie came across these primes. Do they have any applications?

 

[Sudharaka]

Why did Germain come up with her Germain primes? I am intrigued to know why Sophie came across these primes. Do they have any applications?

Hi matqkks, :)

Yes they do have applications. As the following article points out they are applied in Cryptography.

Sophie Germain prime - Wikipedia, the free encyclopedia

Also I have seen these being applied in certain Homomorphic encryption instantiations like the following,

https://eprint.iacr.org/2011/279.pdf

 

[Nono713]

One reason they are useful for crypto is that if you set $p = 2q + 1$ for some large prime $q$, then the order of $(\mathbb{Z}/p\mathbb{Z})^\times$ is equal to $\varphi(p) = p - 1 = 2q$ which is not smooth (in fact, in a sense it is optimally non-smooth since $p - 1$ will always be even). Many group-theoretic integer factorization and discrete logarithm algorithms basically rely on the order of the group being smooth. So choosing such a $p$ helps thwart those methods.

It should be noted that while this is (to my knowledge) still useful for constructing difficult discrete logarithm problems, it is no longer very useful in the case of integer factorization for two reasons:

- current integer factorization limits (150-digit semiprimes or so, i.e. 75-digit primes) operate on numbers so large that $p - 1$ is unlikely to be smooth over any reasonable factor base anyway
- the elliptic curve method (ECM) factorization algorithm does not operate on the multiplicative group of integers modulo $p$, but on a random elliptic curve over the field $\mathbb{Z}_p$, which has an order anywhere in the interval $p + 1 \pm 2 \sqrt{p}$, and some of these curves are going to have smooth order no matter what $p$ is (in other words, you cannot efficiently defend against this algorithm). In fact, very accurate bounds on the probability of finding a smooth curve as a function of $p$ are known, which shows that the algorithm is ridiculously efficient, but, sadly, still subexponential time. But I digress.

Another possible use is in primality testing, using Lagrange's theorem (see Pocklington's primality test for details). The natural generalization of Sophie-Germain primes are called Cunningham chains, which are finite sequences of integers of the form $p_{i + 1} = 2p_i + 1$ such that all $p_i$ are prime.