The Mathematics of Encryption: Prime Numbers

The Mathematics of Encryption Prime Numbers
Photo by Markus Spiske on Unsplash

Many of us know that prime numbers have no positive divisors other than themselves and 1, and they continue as 2, 3, 5, 7, 11, …. But why are prime numbers important? What do we do in our daily life?

Every integer greater than 1 is either a prime number or is a product of prime numbers. For example, while 11 is a prime number, the number 12 is obtained by multiplying the prime numbers as 24=2^2\cdot3. In other words, every integer greater than one is actually produced by prime numbers. This makes them central to the science of number theory, which explains how numbers relate to one another.

The Importance of Prime Numbers for Encryption

Prime numbers also form the basis of encryption. In the RSA encryption method, which is widely used in data encryption of e-mail and other digital transactions today, data is encrypted using prime numbers. Thus, unwanted persons are prevented from accessing the data. In this method, where the product of two large prime numbers is used as the encryption key, the selected prime numbers remain hidden, and only the person who knows the prime numbers that are the factors of this key can decrypt it. Since it is difficult to factor large numbers into primes, the RSA encryption method uses as many prime numbers as possible, thereby increasing the security of the encryption.

How Do We Find Prime Numbers Between Certain Numbers?

25 prime numbers between 1 and 100 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) we can easily write But it is not easy to list larger prime numbers, such as the prime numbers between 1 and 100,000,000. Because there is no regular pattern among prime numbers, a formula cannot be written to generate all prime numbers. When we look at the first 25 prime numbers, it can be seen that there is no regular pattern among the numbers. To construct a list of prime numbers, we must evaluate each positive integer one by one to decide whether it is prime or not. However, considering large numbers, it will take a lot of time to create a list of prime numbers with this method.

YouTube video
Is there a pattern in prime numbers?

While we don’t have a formula that easily generates all prime numbers, we do have a formula that approximates how many prime numbers exist between 1 and a given number of n (including n):

\frac{n}{ln (n)}

The ln(n) in the formula is the natural logarithm of n and is found in almost all calculators. The real value of the prime numbers in the given range is shown with the prime counting function \pi(n).

For example, there are \pi(1,000) = 168 prime numbers between 1 and 1,000. The formula gives us approximately \frac{1,000}{ln(1,000)} = \frac {1,000}{6.908} \approx 145. The accuracy of this calculation is around 86%. When we calculate how many prime numbers between 1 and 100,000 using the formula, the accuracy rate rises to 90%. In fact, there are exactly 9,592 = (\pi(100,000) =  9,592) prime numbers among these numbers, while the formula gives approximately \frac{100,000}{ln(100,000)} = \frac {1,000}{11.51} \approx 8,686

When the number n is chosen large enough, the ratio of the number of prime numbers in the range calculated by the formula and the number of prime numbers, in reality, becomes almost equal to 1. In other words, the accuracy rate of the formula reaches 100%.

This result is known as the prime number theorem. Although we do not know according to which rule the prime numbers, which have an important place in encryption, are distributed among integers, we can approximately calculate the number of integers.

If you are interested in “prime numbers”, you should read “The Solitude of Prime Numbers.”

Ali Kaya


Ali Kaya

This is Ali. Bespectacled and mustachioed father, math blogger, and soccer player. I also do consult for global math and science startups.