Mathématiques - Chiffrement et Encodage

Prime numbers: the guardians of your information

While numbers are a part of our daily life, a special type - prime numbers - has fascinated mathematicians for centuries. Their seemingly random distribution hides surprising patterns and countless applications, from building blocks of numbers to securing our online data.

Most if not all of us use numbers in our daily life: on our phones, in our sales, on road signs… Though abstract in essence, they present a means of quantifying our world. There is however a special type of numbers which has captivated number theorists and mathematicians for centuries: prime numbers.

They have been studied extensively from as early as the days of Pythagoras (ca. 570 – 490 BCE), Euclid (ca. 325 – 265 BCE) and Eratosthenes of Cerene (ca. 276 – 194 BCE) and yet we still have a lot to learn about them.

What are prime numbers?

Put in brief definitions, a prime number is one such number greater than or equal to two that has only two divisors: one, and itself—note that a number D is called a divisor of a number N if N can be partitioned equally into D units, with a remainder zero, for instance we may call 3 a divisor of 6 since 6 can be partitioned into two equal parts of 3 units.

Listing the first 10 prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… we can start making general observations about them: they are all odd, except for 2 who is the only even prime number, and all primes who are greater than 10 have their unit digit either a 1, 3, 7, or 9. Such observations allow mathematicians to classify primes into different classes and study their behavior, recognizing around 75 of them. Such classes include:

1.       Palindromic primes, which are prime numbers that can be read the same way from left to right and from right to left, for example 131, 757. These numbers (with the exception of 11) have all an odd number of digits. and it remains one of mathematics’ open questions whether palindromic primes are finitely or infinitely many.

2.      Twin primes, which are prime numbers with a gap of 2 between them, such pairs include: (3, 5), (5, 7), (11, 13) etc. 5 is the only prime number present in two twin pairs, and all twin pairs greater than (3, 5) can be expressed as: (6n-1, 6n+1) where n represents a natural number. Note that this does not imply that all numbers of the form (6n-1, 6n+1) are primes, consider for instance: (35, 37) = (6x6-1, 6x6+1).

3.      Cousin primes, which are prime numbers that differ by 4 such as (13, 17), they could be written as (p, p+4) where p represents a prime number.

4.      Sexy primes, which are prime numbers that differ by a factor of 6, “sex” in Latin, from where the pun in the naming, for example (5, 11), (61, 67).

Though seemingly counterintuitive, proving that there are infinitely many primes of the above categories is quite tricky. Significant contributions to the countability of twin primes have been made by Zhang, Tao, Baibekov and Durmagambetov among others, yet no formal proof has been presented for the twin prime conjecture (unproved theorem) stating that there are infinitely many twin primes. Similarly, roughly ten years ago in August of 2014, the Polymath group was able to link the countability of the last two classes to proving yet another conjecture relating to the distribution of prime numbers, the Elliott–Halberstam conjecture. However capricious the problem of countability may seem, we know thanks to Euclid that the number of primes is infinite.

Alright… but how to the primes impact us?

The above definition allows mathematicians to split the integers into two main categories: prime numbers and composite numbers. Primes which cannot be further divided, and composites which can be written as a product of at least two other numbers. As it turns out, any given integer can be expressed in a unique way as the product of primes, giving way to The Fundamental Theorem of Arithmetic, or the Prime Factorization theorem. The number 180 for one can be expressed uniquely as: 22x32x51. Hence, it is quite righteous for primes to be referred to as “the building blocks of numbers”.

Not only this, but prime numbers also have huge applications in our daily lives notably in cryptography, the science concerned with the encryption of data, protecting it from being stolen, modified or compromised by scrambling it through mathematical models into a secure code that can only be accessed through a unique digital key.

Primes in cryptography

Plainly put, prime numbers are at the heart of encryption, specifically in the RSA encryption method which is widely used in mails, online transactions, VPNs, Web Browsers etc. For computers, calculating the product of two or more prime numbers is an easy task, the converse can however get really tedious, getting the original prime numbers which build a large composite through prime factorization, is hefty work even for supercomputers. Thus, in the RSA method, encryption keys are chosen to be the product of large prime numbers and only those who know the original primes that build the key can decrypt the code. As Akash Peshin, an Electronic Engineer from the University of Mumbai, India puts it, if a hacker or thief attempting to crack a 400-digit encryption code that secures credit card details, with a computer that tests 1 million combinations per second, would take them around 10194 seconds to accomplish the feat which is tremendous compared to the age of our Universe who is around 1018 seconds old… And the larger the primes are, the harder the decryption becomes. Thus, large prime numbers, which could be very hard to find, have a huge importance in keeping our data safe…

On small scales, the partitioning of prime numbers along the number line seems entirely arbitrary, on large however, primes start to pop-up following patterns that are so hard to describe. The best handle mathematicians have on these patterns is the Riemann Zeta Function  on which the German mathematician Bernhard Riemann (1826 – 1866) had based his hypothesis. The  Riemann Hypothesis could grant us the ability of predicting the distribution of prime numbers along the number line, which would be revolutionary to cryptography.

As you may have guessed, the hypothesis remains unproven till this day, and other than the accompanying social veneration, a massive 1,000,000 USD awards is awaits the mathematician who proves it! 

Good luck for all!