The largest prime number [1]—discovered by a group of scientists led by Patrick Laroche in 2018—drew considerable interest [2]. To better describe the greatness of this number with 24,862,048 decimal digits, we can give the following example: if we print this number on both sides of A4 papers with standard font sizes, the height of these papers placed on top of each other would be 83 cm. Why did these scientists go to such lengths to make this discovery? Why did such a discovery receive so many awards? These questions will lead us on a voyage into the mysterious world of mathematics.

History of prime numbers

A prime number is a positive number which is evenly divisible only by itself and 1. They start with 2, are followed by 3, 5, and 7, and seem to follow no discernible pattern after that. They have always compelled attention as many scientists have tried to come up with a formula to produce them for centuries. According to the available resources, the oldest study on the matter started with Greek polymath Eratosthenes (BC 276-195) and his famous sieve [3]. The sieve of Eratosthenes systematically eliminates composite numbers—the numbers that are not prime—and defines the remaining numbers as prime, but it is very hard to use for large numbers. In comparison, the Mersenne Theorem [4], developed by French scientist Marin Mersenne (1588-1648) and formulated as  (n is a natural number), helps us to calculate many prime numbers. Although it was later found that 2047 () is composite, all prime numbers calculated by this formula came to be referred to as Mersenne primes. The largest prime number discovered in 2018, too, is a Mersenne prime that satisfies this formula.

Another French mathematician, Pierre de Fermat (1607-1665), adopted a similar approach to Mersenne’s and stated that the formula (m is a natural number) can give us prime numbers—but exceptions to this formula have demonstrated that the formula may not always produce primes [5]. These numbers were called Fermat numbers and worked better than Mersenne numbers [6].

Today, it is generally accepted that there is no formula that can give you all prime numbers. Therefore, mathematicians focus on methods to check whether a number is prime. Researchers have come up with various primality tests including the Fermat, Miller-Rabin, AKS, and Lucas-Lehmer to determine if very large numbers are prime.

In addition to prime numbers, mathematicians also refer to the numbers that are relatively prime, i.e., coprime numbers. Take 21 and 10. Although both of these numbers are not prime, they are relatively prime as the two numbers have only one common divisor, 1. Many composite numbers can be coprime with any other number.

Prime numbers and encryption

We use prime numbers every day without even realizing it. It is possible to give examples of how they are used in many fields including physics, engineering, coding, and diverse technological applications. Cryptography or the practice of cryptography is one of the areas where primes are frequently employed. Deriving from ancient Greek words of “kryptós” meaning “hidden or secret” and “graphein” meaning “to write,” cryptography refers to the study of techniques for secure communication. One of the early applications of cryptography involves the use of the Caesar cipher [7].

Caesar cipher.

The Caesar cipher employs systematic encryption; letters are assigned to numbers:

A=0, B=1, C=2 … Z=29

Then, the message is encoded:

S E L A M

21 5 14 0 15

Using a “key” (for instance, adding 5 to each number), the message is encrypted before it is sent:

26 10 19 5 20

The recipient of the message decrypts it using the rules of modular arithmetic (in this case, by subtracting 5 from the numbers). What is crucial here is to be able to communicate the key to the recipient in a secure manner. During the Second World War, German scientists aware of this problem used the Enigma system, where the key would be changed every day during the war [8]. The British used machines developed by mathematician and logician Alan Turing (1912–1954) to decode the encrypted messages despite the fact that keys were changed on a daily basis, thereby changing the course of the war.

Enigma cipher machine used by Germans.

Prime numbers come to our rescue in solving the security problem in systematic encryption. The communication between the sender and the receiver is established using the method called “asymmetric encryption” without using any key. In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA encryption method—the name deriving from their surnames—in which communication is secured between the sender and the receiver by using two primes and a third number obtained by multiplying the primes [9]. The first of these primes is called “open key” which is publicly available. The second prime is the “special key” known to each user. The third number, which may not be prime, is a prime obtained by multiplying the first two numbers. Through special operations, the system matches these prime numbers and the key is encrypted. For example, when you insert your bank card to an ATM machine, your card gives the bank’s publicly available key (prime number) to the machine. Then, the machine asks you to enter your PIN, which does not have to be a prime number, for secure communication with your bank. When you enter your PIN correctly, the system has access to the private key through some special operations in the background and allows you to perform transactions related to your account. This process relies on complex algorithms for ensuring security. Whichever algorithm is used, all encryption and decryption operations are performed using prime numbers. The larger the prime number, the harder it will be to break the code.

As is seen, we frequently use prime numbers in our daily life—often without even being aware of them. There may be undiscovered properties and novel areas of the use of prime numbers.

References

1. "Great Internet Mersenne Prime Search", www.mersenne.org

2. "Largest known prime number", en.wikipedia.org/wiki/Largest_known_prime_number

3. "Sieve of Eratosthenes (Eratosthenes'in Eleği)", tolpp.com/sieve-of-eratosthenes-eratosthenesin-elegi/

4. "Marin Mersenne", www.mathematik.ch/mathematiker/mersenne.html

5. "Pierre de Fermat", www.spektrum.de/wissen/pierre-fermat-1607-1608/962953

6. →prime
→prime
→prime
→prime
→composite
→prime
The sequence of Mersenne primes in the binary number system.
→ prime
→ prime
→prime
→prime
→prime
→composite
The sequence of Fermat primes in the binary number system.

7. "Caesar cipher", en.wikipedia.org/wiki/Caesar_cipher; "Caesar Cipher Exploration", en.khanacademy.org/computing/computer-science/cryptography/crypt/pi/caesar-cipher-exploration

8. "Enigma machine", en.wikipedia.org/wiki/Enigma_machine

9. "What is RSA encryption and how does it work?", www.comparitech.com/blog/information-security/rsa-encryption/