Number Theory and Cryptography


What is number theory?

“Mathematics is the queen of the sciences and number theory is the queen of mathematics.” – Guass

There are few main branches of pure mathematics. One of them is Number theory. Number theory is mainly related to the study of integers and integer-related functions.

When we talk about numbers, it goes back to ancient history when the ancestors learned to count or had the idea of counting. It can be recognized as the initiation of the study of numbers. In the early stages, they didn’t have the concept of numbers, but the idea of counting and multiplicity which were essential for their daily survival.

And the facts of a well-defined number system go back to the ancient civilizations of Mesopotamia, Egypt, China, and India. And the study that was initiated as a method of counting developed with time on the shoulders of well-known Mathematicians such as Pythagoras, Euclid, Fermat and many more.

And modern-day Number theory contains from Natural numbers to many more fascinating propositions, theories, and conjectures(statements believed to be true, but haven’t been proved yet). The main thing about scientific subjects such as Mathematics is we don’t have any limits. So as a sub-branch of mathematics, Number theory is also a field that is ever-growing. 

Some interesting topics/theories in Number Theory

Infinite number of Pythagoras triples

Pythagoras triple is a set of 3 numbers, where one number’s square can be expressed as the summation of the squares of the other 2 numbers.

Ex :- 32 + 42 = 52

When you find a Pythagoras triple, you can multiply all 3 numbers from a natural number which gives you another set of Pythagoras triples.

32 + 42 = 52 multiply both sides by n2 where n is a natural number.

Which gives you (3n)2 + (4n)2 = (5n)2 so (3n,4n,5n) is also a Pythagoras triple. And this proves there are infinitely Pythagoras triples.

But that doesn’t mean every Pythagoras triple shouldn’t be in this form.

We can prove that a set of 3 numbers is a Pythagoras triple if and only if the numbers are in the form of (x,y,z) where x = st, y = (s2t2)/2, z = (s2+t2)/2 or an integer multiple of such a solution.

What if the indices of the numbers are greater than 2?  Consider xn + yn = zn

Are there any triples of positive integers that satisfy this equation?

This was one of the most questionable conjectures in the history of mathematics where Fermat stated that no integers satisfy the equation when n is grater than 2 which is known as Fermat’s last theorem.

It stayed as a conjecture for centuries until mathematician Andrew Wiles proved the theorem.

Lagrange theorem in number theory

Every positive integer can be expressed as the sum of 4 perfect squares. The sum can be not unique but there is at least one way of expressing as the sum

Ex :-

51 = 52+52+12+02

23 = 32+32+12+22

31 = 52+22+12+12

But every integer can’t be expressed as a sum of 3 perfect squares. 

Ex :- 7 can’t be expressed as a sum of 3 perfect squares

It can be easily shown that any number can be expressed as a sum of 5 or more perfect squares. (We know that a number can be expressed as a sum of 4 perfect squares. So we have to just ass 02 as far as we need.)

Infinite number of primes

A prime is a number which has no other divisors except itself and 1 (Ex:- 2,7,11)

It is not quite obvious to say that there are infinitely many primes. But we can form an algorithm to find primes.

Suppose that you know first n different primes. (p1,p2,…….,pn)

It can be shown that p1*p2*…..*pn+ 1 is the n+1th prime.

So by induction, we can show that there are infinitely many primes.

Twin Primes Conjecture

Twin prime conjecture states that there are infinitely many pairs of (P,P+2) where both numbers are prime.

Ex :- (5,7) is a pair of twin primes.

As mentioned in the topic, it’s still a conjecture, which means even though it’s believed to be true, still hasn’t been proven. But using modern computers, the largest twin primes that have been calculated is 2996863034895 * 21290000-1, s 2996863034895 * 21290000+1 which have 388342 digits each.

Why is number theory important?

After reading the last part, you may wonder “why do we learn number theory?”

The number 1 reason is, obviously the beauty in number theory. Learning and practicing number theory is like an art. Also, it can be considered as playing a game. Once you start to admire the beauty in number theory (even any branch of mathematics) it’s harder to escape from the beauty of mathematics.

Apart from that reason, there are some fields where number theory is largely used. 

A notable incidence in mathematics is from the theorems and conjectures that we know today, only a small percentage is used in other fields. But the important point is we don’t know whether what we find today will be used in the future or not. But there are many cases, after years of finding the theorem, using it in a field that is completely different from number theory. (Reimann’s theory of curved spaces was used after years in Einstein’s theory of relativity)

Here I will talk about one such field: Cryptography.

What is Cryptography?

Cryptography is the practice and study of hiding information. (Ex:- codifying a massage in order to prevent its content from unwanted eyes)

We don’t need to talk about the uses of Cryptography separately. In almost every field, cryptography is used to hide sensitive information.

What is the role of Number Theory in Cryptography?

Cryptography mostly consists of encoding and decoding a massage, that can be only accessed by the 2 parties involved.

Using number theory, methods of encoding and decoding can be developed where it’s almost impossible to be broken by a 3rd party. 

Many methods of encoding and decoding (known as cryptosystems) but we will briefly discuss methods that use number theory.

The RSA Cryptosystem

The basic idea that is being used in this method is when we get 2 larger primes (let p,q), even though we can easily find the n = p*q (multiplication of 2 primes), when we are given number n, it’s difficult to generate p and q (Prime factorization of n). So the security in the decoding increases as we choose much larger p and q. When the numbers are larger, it is difficult to factorize them even using modern computers as factorizing can only be done using random checking method.

So one party thinks of p and q and tells the number n and another number e (which should be a relative prime of (p-1)(q-1)) to the world. So the one that wants to send the message gets those 2 numbers and decodes the message using a mathematical function that involves numbers n and e. 

And when he sends the result, in order to decode it, the other party needs the prime factorization of n which is only known by the receiver.

One can break this only if he knows p and q. As finding p and q when you know n is really hard, it’s really hard to break the message.

This method is mostly used on the internet when credit card numbers and other such sensitive data are requested.

An important fact:- 

There is no exact algorithm that can be used to factorize or identify whether a number is a prime or not.

The only method of determining is trial division by primes less than the number. Imagine there is an ideal processor which can do a trillion (1012) trial divisions per second. If we set up million of those processors parallel where each processor takes a different subset of primes for trial checking, then we are able to trial check 1018 primes per second. If the smallest prime divisor of the number we are checking has 50 digits, we can show using prime number theory, there are about 8.7*1047 primes before the 50-digit prime, so we have to trial check for 8.7*1047 primes.

So, using the previous ideal setup, it will take nearly 1022 years to complete the trials, apparently, our universe is only 2*1010 years.

The only method of breaking the RSA cryptosystem is factorizing the number, but as we stated it is impossible.  

This is the reason that the RSA cryptosystem makes a quite secure method of decoding and encoding messages.

This is only a single field that uses number theory. There are many other fields that use number theory. Apart from the beauty of number theory, these important uses of it make number theory more and more interesting.


Written by: Thishanka Alahakoon


Image Courtesies

Tagged : / / /