Reimann Hypothesis And Its Connection To Cryptography

Over the centuries, mathematicians have been involved in solving some of most complex problems. But what is the motivation behind that? The pursuit of truth! But The Clay Mathematics Institute thought that there should be a little more than that. So to celebrate mathematics in the new millennium, they established seven Millennium Prize Problems. The prize money for each problem is one million dollars. That’s pretty exciting! These were some of the most difficult problems over which many mathematicians were racking their brains. Reimann Hypothesis is one of them. The interesting thing about this particular problem is that it has far reaching consequences in the field of modern cryptography and internet security. Now how can an obscure and complex mathematical problem affect cryptography and internet security?  

It all starts with prime numbers

Some numbers have the special property that they cannot be expressed as the product of two smaller numbers. Such numbers are called prime numbers. For example, the number ‘3’ cannot be expressed as a product of two numbers other than 1 and itself. Same is true for 2, 5, 7, etc. Why do we care about prime numbers? Well, the distribution of prime numbers among all natural numbers does not follow any regular pattern. It means that their occurrence is random by their very nature. There is no precise formula to predict when the next prime number will occur. This property of prime numbers has been utilized extensively to build most of the modern security systems.

What is Reimann Hypothesis?

Berhard Reimann, a German mathematician, was working on prime numbers when he noticed something interesting. His findings led him to believe that the primes are distributed as regularly as possible given their seemingly random occurrence on the number line. He observed that the frequency of prime numbers is very closely related to the behavior of the function:

ζ(s) = 1/1^s + 1/2^s + 1/3^s + 1/4^s + …. upto infinity

This is called the Riemann Zeta function. The complex variable ‘s’ can take any value.  His work gave an ‘explicit’ formula for the number of primes less than a given number ‘x’ in terms of the zeros of the zeta function. The zeros of a function are the values of the input variable for which the function becomes 0. This function predicts the distribution of prime numbers. The reason this is a “hypothesis” and not a theorem is because he was not able to mathematically prove it.

Why should I care about some random function?

We know that the above series converges when s > 1. It means that if you compute the sum up to infinity, it will be a finite value. People have asked what happens when we treat ‘s’ as a variable in the complex plane. It turns out this new function is related to prime numbers. The function has zeros at the negative even integers and in a small strip (between 0 and 1). Reimann’s Hypothesis says that all these extra zeros have real part equal to 1/2. If this is true, it implies that the primes are well spaced. Although he postulated it, he was not able to prove it. This problem has been around 160 years and nobody has been able to disprove it either. A proof that it is true would shed light on many of the mysteries surrounding the distribution of prime numbers. If you are interested in looking at a friendly mathematical explanation, you should definitely check out this link.

How is it related to cryptography?

The whole of modern cryptography is based on the fact that prime numbers occur sporadically. All the crypto algorithms, protocols and standards are built on the belief that predicting the next occurrence of a prime number is not possible. Hence an attacker will have to try all possible combinations to actually break into a system. Based on the current strength of these algorithms and the power of computers, it usually takes around 20-30 years on an average for an attacker to brute force it. But if Reimann Hypothesis were to be true, then it will greatly simplify the job of the attacker.

Let’s consider a simple example. We have an encryption system in place. If somebody were to brute force this particular system, it will take around 1000 days to break it. Now once the attacker starts, his machine will have to continuously work for 1000 days before he can break into the system. It usually takes some time for the system admin to realize that the system is under attack. Let’s say we have a bad system admin and he realizes that the system is under attack after 600 days. He goes and immediately changes the system settings, and the attacker is back to square one. 600 days of work down the drain!

Now the Reimann Hypothesis is so powerful that it will reduce the attack time to one day. Pretty damn impressive right! It has the capacity to shake the very foundation of internet security. This is the reason people are pursuing this with such fervor. This blog post is an extremely simplified version of the problem. The real mathematical formulation is very complex, but very interesting too! If you are a fan of number theory, you should definitely give it a good read. It has far reaching implications in the field of number theory, cryptography and many other fields as well.

———————————————————————————————————–