Why study prime numbers ?

Prime numbers have several properties which render them extremely important in numerical applications, both on the theoretical side, and as a practical tool.  Probably the most important aspect of prime numbers is that they indicate what cyclic modular rings are fields, that is, in what cases one can calculate a multiplicative inverse of every number in a modular ring.   They have other properties too.  The fact that every integer can be written as a unique product of prime numbers is another important reason why prime numbers are important: they permit to code any set of integers onto one single integer, which is the product of the powers of successive primes with the integers to be coded.

Relative prime numbers and Euler's Phi function

Two integers are relative prime, if they have no other common divisor but 1.  For instance, 8 and 15 are relative prime: their divisors (for 8, this is {1,2,4,8} ; for 15, it is {1,3,5,15}) only have 1 in common.  Of course, every prime number is relative prime to any other integer, but, as we saw, integers which aren't prime can be relative prime.  In a modular ring, all elements which are relative prime to the modulus have a multiplicative inverse.  Of course, the divisors of the modulus aren't relative prime to the modulus, and hence, they don't have an inverse: this is why a modular ring with a non-prime modulus cannot be a field.   1 is also considered relative prime to any number although officially, 1 is not a prime number.

If we have a modular ring with modulus M, then the number of elements that have a multiplicative inverse is equal to the number of integers that are smaller than M and which are relative prime to M.  That number is used to define a funny function over the positive integers: Euler's Phi function.

Euler's Phi function, Phi(M), is equal to the number of relative prime numbers to M, smaller than M.  One can also say that Euler's Phi function indicates how many elements of the modular ring with modulus M have a multiplicative inverse.

A simple and straightforward, but immensely slow method of finding Phi(M), is by running over all numbers 2, 3, 4, .... M - 1, and calculating the GCD of that number with M.  Each time it is equal to 1, we know that we have a number, relative prime to M, and hence that that number has a multiplicative inverse.

There is a very important theorem giving the value of Phi(M) without having to do the above procedure.  It tells the following:

M can be factored in prime factors in the following way:

M = (p1)e1  (p2)e2 .... (pk)ek

then: Phi(M) = the product of the numbers [ (pi)ei - (pi)ei - 1 ]

For instance, if M = 60, then we write M as a product of prime factors:  60 = 22 31 51

The formula for Phi(60) is then [ 22 - 21 ] [ 31 - 30 ] [51 - 50 ] = [4 - 2] [3 - 1] [5 - 1] = 2 . 2 . 4 = 16

In the modular ring with modulus 60, there are 16 numbers relative prime to 60 (there are 16 elements that have a multiplicative inverse).

Note that this implies that Phi(p) = p - 1 if p is prime, but this, we knew already: in a prime modular ring, which is a field, there are p - 1 elements which have an inverse (0 never has an inverse).

Euler's theorem

We recall Fermat's little theorem:

ap = a (mod p)

where a is an integer, and p is a prime number.

We can also write it as:

ap - 1 = 1 (mod p)

Euler's theorem is a generalisation of Fermat's little theorem, in the following sense:

aPhi(m) = 1 (mod m)

In the case m is a prime number, this reduces to Fermat's little theorem because Phi(p) = p - 1.  But Euler's theorem is valid for any integer.

Primality tests

It is often necessary to select (randomly and secretly, or publicly) a very large prime number.  The standard way of finding out whether a given integer is a prime number, is to do an Euclidean division by all candidate prime dividers up to the square root of the number under question.  However, this becomes not practical when we are talking about very large prime number candidates, as the test would require too many divisions to be performed.

Unfortunately, there don't exist exhaustive and certain primality tests for very large numbers.  What does exist, are statistical tests, that have a very small probability to make a mistake.  These tests actually only make a mistake in one direction.  If they qualify a number as not being a prime, then this is 100% certain.  If, however, they qualify a number as being a prime, then there is a small probability that they make a mistake.

Grossly, the density of prime numbers goes like 2/ln(N), that is, the probability that a large (uneven) number N is a prime number, is about 2/ln(N).  A way to find a "random" (and secret) prime number of k digits is to pick a random integer of k digits, q, and testing q, q+1, q+2, .... on primality ; the first one in the series that turns out to be a prime number is then chosen.  With the density of prime numbers as given above, it roughly means that if we want a prime number, of, say, about 1024 bits, about 1 uneven number out of 354 is a prime number, so one has to try on average 354 uneven numbers starting from a random integer, before one will hit a prime number.  The number of expected trials before hitting a prime rises proportionally to the number of bits in the desired prime.

Fermat primality test

This test is based upon Fermat's little theorem.  The test is the following:

1. pick randomly a test number a in the set {2,3, ... p-1}
2. calculate ap-1 mod p
3. if the result is not 1, then p is not a prime number -> stop
4. if the result is 1, go back to step 1 until bored

This test is sure if we scan over all values of a, but that's of course impossible.  As such, we only pick statistically some values in step 1.  The more times we run through these steps, and the number "survives", the larger are the chances that it is a genuine prime number.

The problem with the Fermat test is that there is a small set of numbers, the so-called Carmichael numbers, that are not prime numbers, but that will get through the test as long as the numbers a picked in step 1 are relative prime to p.  It is estimated that about one number in 10 billion is a Carmichael number.

Miller-Rabin primality test

A test that avoids this problem, and is now the more standard way of testing for primality, is the Miller Rabin test.  It goes as follows.

1. find the decomposition of p - 1  = 2u r (that is, for a prime candidate p, find u and r)
2. pick randomly a test number a in the set {2,3,...p-1}
3. verify that ar mod p is not 1 or p - 1  (if it is, go directly to step 8)
4. replace a by a2
5. if the new a is equal to p - 1, go to step 8
6. if the new a is equal to 1 then p is not a prime (we can stop)
7. repeat steps 4-7 until we have squared a (u - 1) times
8. if we haven't found yet an indication that p was composite, go to step 2 until you are tired
9. if p survived until here, it is most probably a prime

The Miller-Rabin test is based upon Miller's theorem, that states that for a given integer p which is not a prime, the above test fails to detect that it is not a prime for numbers a (picked in step 2) in less than Phi(p)/4 cases.  That is, when picking an a, if the Miller Rabin test works out, it already indicates with a probability of at least 75% that p is a prime.  Picking another a increases this probability to 87.5%.  And so on.  The Miller-Rabin test is quite good at finding the non-primality of Carmichael numbers, which was the failure of the Fermat test.