In this data project of Math 1a Spring 2021
(see [PDF]), I had modified a picture of
Germain to make it more accessible (as most all known pictures of Germain are terrible).
I learned about Sophie Germain primes (primes for which p and 2p+1 are primes during Cryptology military services. We all had been
working there on integer factorization and related things like discrete log problems.
Sophie Germain primes behave better in RSA schemes or key exchange set-ups.
See this handout [PDF] about
cryptology.
Germain primes behave similarly as prime twins as in both cases
we do not know whether there are infinitely many and because in both cases, the density in the range n is of the order
1/(log(n)^2. This is motivated by probabilistic thinking assuming that p and 2p+1 are prime independent of each other.
GermainePrimeQ[n_]:=PrimeQ[n] && PrimeQ[2 n + 1];
GermainePrimes[n_]:=Select[Map[Prime,Range[n]],PrimeQ[2#+1]&]
|
Update of February 28, 2025: In episode 7 one can see a text with the really
silly statement that the number of Germaine primes grows simlarly as the number
of primes. Empirically the fraction is log(n). If A(n) is the number of primes less
than n and B(n) is the number of Germaine primes less than n, then (B(n)/A(n)) ~ 1/log(n)
of course this is all experimental, as nobody has shown the infinitude of Germaine primes.
But you can try yourself and see how silly the Prime Target movie can be at times:
F[n_]:=Module[{A = Map[Prime, Range[n]],B},B=Select[A,PrimeQ[2#+1] &];
N[Log[n]*Length[B]/Length[A]]]; F[1000000]
|
Here is an interesting riddle which can be solved while waiting in line somewhere.
(I made up the problem and solved it once while running):
|
"The safe prime q=2p+1 for an odd Germaine prime p has the property that
it is a quadratic residue modulo an other prime s if and only if that prime s is
a quadratic residue modulo q."
|
|
|
