Skip to main content

Prime Numbers and Encryption

Mathematics
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.
| Mehmet E. Altin | Issue 154 (Jul - Aug 2023)

This article has been viewed 4394 times

Prime Numbers and Encryption

In This Article

  • 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.
  • 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.
  • 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.

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].

German Spy Museum Berlin - History of espionage

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.

Chiffriermaschine Enigma im Deutschen Spionagemuseum Berlin

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/


More Coverage

Covid Resilience

The recent pandemonium enveloping us all unsheathes a swashbuckling double-edged sword advancing our retreat into global disconnect may our union reunite beating swords into plowshares

The Web of Arrogance and the Centrifugal Force of Sincerity

Question: Arrogance is a serious character problem we experience throughout our lives. We falsely claim ownership over every good deed we are involved, forgetting that they are blessings from God. How can believers cope with such an arrogance?  O...

The Theological Dimension of the Thought of M. Fethullah Gülen (Part 2)

“Sincerity” in the Islamic Tradition Ikhlas is a Qur’anic concept that is variously translated as “sincerity” or “purity of intention,” and Gülen’s understanding of this term covers both aspects of the Qur’anic concept. In ordinary parlance, “sin...

Racial Disparities

American history is lined with clear examples of overt racism from slavery to the implementation of the Jim Crow Laws, and many other examples that have taken years of struggling to dismantle. However far we seem to have come current events such a...