Sophie Germain cipher and prime numbers – 05/31/2022 – Marcelo Viana

Sophie Germain discovered her profession in mathematics as a teenager, through her father’s books. The family rejected such an “inappropriate” occupation of a girl from a family in 18th century Paris, but she persevered and eventually achieved a reputation among the best mathematicians of her time.

Reading “An Essay on Number Theory”, published by Adrien-Marie Legendre in 1798, and “Mathematical Investigations” (“Disquisitiones Arithmeticae”), written by Carl-Friedrich Gauss in the same year and published in 1801, awakened his taste for number theory, which would be his main research topic.

His most famous works relate to the theory of FermatAccording to the equation x^number+ p^number= z^number It has no integer solutions when the exponent n is greater than 2. The known results dealt with specific values ​​of the exponent: n = 4 (Fermat, 1670), n = 3 (Euler, 1770) and n = 5 (Legendre and Dirichlet, 1825) .

Germain was the first to deal with an entire family of exponents: she proved that if n satisfies certain conditions – which apply to all integers less than 100 – then any solution to the equation must be such that some number x, y, or z is a multiple of n (first case of Fermat’s theorem). In fact, this was the first step in an ambitious plan to prove the general state of the theory. It ended in failure, but Germaine’s pioneering spirit is still impressive.

The terms of Germain’s theorem are automatically checked if the exponent n is “a prime number of Germain”, i.e. a prime number such as 2n + 1 is also a prime number. The list of German primes begins with 2, 3, 5, 11, 23, 29, 41, … The interesting question is how many are there: it is believed that they are in infinite quantities and that there are at least N / (log N )^two German’s prime is smaller than any given integer N. But no one has yet been able to prove these facts.

Numbers in the form of 2n + 1, with n being prime in Germany, are called “safe primes”, due to a practical application you would never have expected.

The current main methods of coding are based on the fact that it is difficult to determine the factors p and q due to the product of pq made up of two large prime numbers. But this depends on the choice of primes: for example, if p is such that p − 1 can be factored into small primes, it is not difficult to crack the cipher. One way to avoid this risk is to use p and q which are safe primes.

Current link: Did you like this text? A subscriber can unlock five free accesses to any link per day. Just click the blue F button below.