M. LeBlanc and Safe Primes

Sophie Germain (born 1776 in Paris) was a French mathematician and who used safe primes to investigate Fermat’s Last Theorem. She gained…

M. LeBlanc and Safe Primes

Sophie Germain (born 1776 in Paris) was a French mathematician and who used safe primes to investigate Fermat’s Last Theorem. She gained her knowledge of mathematics by studying the works of Euler and communicated her ideas with other famous mathematics scholars including Legendre, Fourier and Gauss.

In fact, at the time, she faced great resistance in her studies, including from her parent who tried to stall her research by confiscating her candles and taking away her clothes. Sophie also hid her gender when communicating with Gauss and used the pseudonym of M. LeBlanc. But, against all the obstacles she faced, she overcame them and even learnt Greek and Latin so that she could read about the works of Euler and Newton.

Sophie Germain prime

A Sophie Germain prime (p) is a prime number which also generates a prime at 2p + 1. 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 (2x17+1), and which can be factorized. These primes have been seen as being important when selecting prime numbers to be used in the RSA method. For this, we create a public modulus (N) and which is the multiplication of two large prime numbers (p and q). If these prime numbers are weak, it can make the factorization of N easier.

The first few Sophie Germain primes are 2, 3, 5, 11, 23, and 29, and which lead to the safe primes of 5, 7, 11, 23, 47 and 59 [here]:

import sys
from libnum import prime_test_miller_rabin


p=11


if (len(sys.argv)>1):
 p=int(sys.argv[1])

flag1=prime_test_miller_rabin(p)
flag2=prime_test_miller_rabin((p-1)//2)

print ("Is p={0} a safe prime?".format(p))
print ("\n prime(p):\t{0}".format(flag1))
print (" prime((p-1)/2)\t{0}".format(flag2))


if (flag1==False):
 print("\nThe number is not prime")

elif (flag1==True and flag2==True):
 print("\nThe prime is safe")
else:
 print("\nNot a safe prime")

Overall safe primes are used in cryptography, as they are robust against attacks within discrete log methods (such as for the Diffie Hellman methods). In the following we use the Miller-Rabin test for primality:

p=47 (safe as 46/2=23) Try!
p=59 (safe as 58/2=29) Try!
p=83 (safe as 82/2=41) Try!
p=99 (Not a prime!) Try!

The largest-ever safe prime found was 2618163402417 ×²¹²⁹⁰⁰⁰⁰ − 1.