Safe Primes, Goldilocks and Riddinghood
As a cryptography professor, I spend a good deal of my time dealing with prime numbers. Basically they are at the core of public key signing and used to encrypt things, prove identities, and also to prove the credibility of digital signatures. So, as you may remember, a prime number is only divisible by itself and 1. So, 15 isn’t prime, but 17 is. In a recent version of Pointless on the TV, there was even a question on naming a prime number less than 200. For me, it was 97, and this is one I use in testing programs. For larger ones, I use 2¹⁹-1 (19 bits) and 2²⁵⁵-19 (256 bits). In most cases, of course, we would pick random prime numbers, and which will make them difficult to crack.
But not all primes are the same.
Safe primes
In cryptography, we often search for safe primes. A safe prime (p) — or also known as a Sophie Germain prime — is safe when 2p + 1 is also prime. Sophie Germain was a French mathematician and who used safe primes to investigate Fermat’s Last Theorem.
A Sophie Germain prime (p) is a prime number which also generates a prime at 2p + 1 — and which is defined as a safe prime. Thus 11 is a Sophie Germain prime, and where 23 is a safe prime. But 17 is not a Sophie Germain prime, as we get 35 for 2x17+1, and which can be factorized. These primes have been seen as being…
