Table of Contents
Number theory is one of the oldest branches of pure mathematics. Of course, it concerns questions about numbers, usually meaning integers or rational numbers. It has many applications in security. For example, the famous public-key cryptosystem RSA is based on some number theoretical results. Next we will go through some fundamental topics.
Pierre de Fermat wasn't a professional mathematician. He was actually a lawyer and government official. But he is absolutely one of the most important figures in the history of mathematics. Many people know the story of his last theorem, Fermat wrote his Last Theorem in the margin of his copy of the Arithmetica:
It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second into two like powers. I have discovered a truly marvellous proof of this, which this margin is too narrow to contain.
And it took more than three hundred years for such a proof to emerge. The quest for a proof of this theorem resulted in the development of several branches of mathematics. The eventual proof of the theorem is more than a hundred pages long.
Fermat's little theorem may be less well known to the general public but is more important in cryptography. It is very simple:
For any prime number n, and for any number a, 0 < a < n, an-1 ≡ 1 mod n.
One application of Fermat's little theorem is primality test, i.e. to tell whether a number is prime or composite. For example, given
n = 31987937737479355332620068643713101490952335301
Is n a prime number? Of course you can try to factor n. If you can find any factor of n, then you can conclude n is a composite number. Otherwise it is a prime number. But we know there is no efficient factorisation algorithm, so it may take you some time. Or you can pick a number between 2 and n-1, for example let us pick 2, and compute 2n-1 mod n, the result is 1281265953551359064133601216247151836053160074. This can be done quite fast using the square-and-multiply algorithm. Then we can immediately conclude that n is a composite number. This is because if n were a prime number, then 2n-1 would be congruent to 1 modulo n based on Fermat's little theorem. But now the result is not 1, therefore n must be a composite number.
Let's try again with another number n = 3778118040573702001. This time 2n-1 ≡ 1 mod n. Can we say n is a prime number? NO! Fermat’s little theorem works in only one direction: there is no "only if" in the theorem. That's means an-1 ≡ 1 mod n can be true even n is a composite number. And indeed if you keep testing, then you will get the following result:
3n-1 ≡ 1 mod n
5n-1 ≡ 1 mod n
7n-1 ≡ 1 mod n
11n-1 ≡ 3434652764157910911 mod n
So 3778118040573702001 is a composite number! Since Fermat's little theorem won't tell us a number is a prime, what we can do is to pick multiple numbers and try then one by one. If one of them failed the test, then we know n is not a prime; if all numbers passed the test, than we have some confident that n is probably a prime number.
But how many test do we have to do before we are confident enough? Unfortunately, it is hard to say. Let's call a number a a witness (for the compositeness of n) if an-1 ≢ 1 mod n when n is a composite number. Apparently, if there are always many witnesses, then we can be quite confident even with just a few test. For example, if we have an algorithm such that for every composite number n, 99% numbers between 2 and n-1 are witnesses, and we choose one number a randomly and it passes the test, then the chance of n being a composite number is lowered to just 0.01. On the other hand, if we have an algorithm such that only 1% numbers are witnesses, and we choose one number randomly and it passes the test, then the chance of n being a composite number is still 0.99 and we need to repeat the test 459 times with different numbers in order to make the probability below 0.01.
In most cases there are more than 50% numbers which are witnesses, so the Fermat primality test goes well. But there are some special composite numbers called Carmichael numbers which have much less witnesses. For example, 3778118040573702001 only about 12% numbers as witnesses; 994788345601, only 0.07%. If n happens to be a Carmichael number, then the Fermat primality test may falsely report that n is a prime number. Although Carmichael numbers are rare, there are infinitely many of them. That's why in practice we usually don't use Fermat primality test. Instead, some sophisticated variants are used. For example, Miller-Rabin primality test and Solovay-Strassen primality test. Miller-Rabin guarantees that for all composite numbers (including Carmichael numbers), the error rate is below 25%. Solovay-Strassen guarantees that the error rate is below 50%. That's means if a number passes the Miller-Rabin test 10 times, then the probability of it being a prime number is 1- 0.2510 = 0.999999. Those tests only produce a probabilistic result. If n is not found to be a composite number, then it can be declared probably prime. If you are uncomfortable with this, there are also deterministic primality test algorithms. For example, the AKS primality test, which is also based on Fermat's little theorem.
Useful Links