The question that is of most interest to cryptographers is very similar to the factoring problem discussed earlier. If I give you a number can you tell me if it is a prime or not. Clearly to prove that it’s not a prime all you have to do is find a non-trivial value, i.e. not 1 or the number itself, that divides it exactly. On the other hand to prove that it is a prime means you have to test all of the possible candidates for dividing it and show that none of them actually do.

Clearly primality testing is difficult. In fact Eratosthenes in 200BC developed the first of the primality testing algorithms but it has the problem of being slow. His method “The Sieve of Eratosthenes” works like this:

• Suppose you want to test n for primality
• Make a list of numbers from 2, to n and begin by putting a circle around 2 and then crossing off all of its multiples
• Next move to 3 and put a circle around it and cross off all its multiples and so on
• When you have finished and every number is either crossed off or circled all you have to do is to see if any of the circled numbers divide n
• If none of them do then n is a prime

This algorithm works but it’s slow and it gets slower as n gets bigger. It simply isn’t a practical method of testing primes.

The problem solved in 2002 is whether or not there is a quick method of testing if a number is prime – to be more precise whether primality testing is something that can be done in polynomial time, in other words in a time that increases only like some power of the size of the number n.

Until the discovery of the new algorithm all primality tests took longer than polynomial time and hence weren’t practical once n got sufficiently big. The AKS algorithm found by Agrawal, Kayal, and Saxena is most simply put as “Primes is in P”.

The 13-line program that tests numbers for primality with certainty faster than any other

Still secure

At this point you might think that the problem is that finding a fast method of testing primes would compromise Internet security. This is not so but the reason it isn’t the case is interesting in itself.

The truth of the matter is that we have had fast procedures that test primality for some time – and they are faster than the new algorithm!

If this seems confusing I should make clear that these algorithms are very different in that they are randomised algorithms and they only guarantee that a number is a prime to any given level of certainty you care to specify. This is a very strange idea and it takes us away from the pure and exact results of the sort of mathematics we have been considering so far, so an example might be a good idea.

Consider the problem of trying to prove that two very complicated formulae, f1 and f2, are in fact identical. It might well be that the algebra needed to reduce one to the same form as the other could take years but working out a specific value is by comparison easy.

Suppose we pick a value x1 and work out the value of f1 using it. If we worked out the value of f2 using x1 and found it was different then we would have proved that f1 and f2 are not identical. On the other hand what would we have learned if they were the same? Well nothing certain but the chance that two different formula give exactly the same answer for a number picked at random is small.

That probability can be made even smaller by repeating the check using a different number, x2, picked at random. This is a randomised test of the identity of the two formula and by picking more and more numbers to test then we can be increasingly certain that the formulae are identical.

Of course this is not a proof but it is often good enough.

Pick a prime, any prime…

To return to primality testing. You might think that the simplest way to create a randomised test that n is prime is to simply pick random values between 2 and n and see if they divide n.

The more you pick and fail to find a divisor the more certain you are that n is prime. While this is a randomised primality test it isn’t a particularly good one and there are much, much better ones, both in terms of the amount of work they require you to do and the level of certainty they provide.

Any number which passes a randomised test with a high probability is referred to as a “pseudo-prime”.

Currently one of the best known and most used test is Rabin’s Strong Pseudoprimality test and it’s interesting enough to explain in more detail.

If the number we want to test is n, assumed odd, first we have to find d and s such that

 n-1=2sd  

where d is also odd (this is easy to do, try it).

Next we pick an x smaller than n and form the sequence:

xd, x2d, x4d, x8d, … xn-1  (mod n)

all calculated modulo n.

Calculating modulo n simply means use “clock arithmetic” with the clock wrapping round to zero at n-1. For example, counting mod 6 goes 0,1,2,3,4,5,0,1,2,3,4,5,0 and so on as the clock wraps round at 5 back to 0 again.

Once you have the sequence of values –  called a “Miller-Rabin sequence” – you can be sure that if n is a prime the sequence ends in a 1.

How does this help with a randomised primality test? Simple, just pick a value of x less than n and compute the Miller-Rabin sequence. If it doesn’t end in a 1, then the number is composite and not a prime. Notice that if it does end in a 1 then this doesn’t prove it is a prime because some composite numbers produce Miller-Rabin sequences that end in a 1.

The reason why this is such a good test is that if n isn’t a prime just less than three-quarters of all the x values you could pick at random produce Miller-Rabin sequences that don’t end in a 1.

So if you pick one value at random and it gives a sequence that ends in a 1 the probability is one in four that it is really a composite non-prime.

Pick 2 and the probability goes down to one sixteenth. If you continue picking M numbers that give a sequence that ends in 1, this means that the probability that you have a non-prime is ¼^M.

For example, if you get sequences that end in 1 with 100 random values then the probability that you have a non-prime number is ¼^10 which is roughly 1/10^61 which is exceeding unlikely and so you are safe in concluding that the number is indeed prime.

Such is the strange reasoning behind randomised testing for primes, and many other randomised algorithms. They never produce certainty but what is the practical difference between a probability of 1/10^61 and certain proof? There is more chance of a machine malfunction giving you the wrong answer computing a certain proof of primality than the Strong Pseudoprimality test failing!

Certainty restored?

So if knowing that a number is probably a prime is almost as good as knowing that it certainly is what’s the fuss about?

There is still the philosophical point that a mathematical proof reveals a deeper truth than some random chance that something is true.

What is more surprising is that the proof is so very simple and that it has remained undiscovered for so long.

Now consider what this means for the rest of the foundation of our cryptographic security. We assume that because something is difficult and because mathematicians have been working on the problem for years, centuries even, that the problem must really be difficult, intrinsically difficult. This is the assumption behind the factoring problem that many code systems rely on.

Suppose now that the next problem Agrawal, Kayal, and Saxena, or some similar group, turn their attention to is factoring. Perhaps what was always assumed to be difficult will turn out not be if a sufficiently fresh approach is taken to the problem.

Perhaps this has already happened.

Answer to the factor problem: 260727302559 and

2760727302517.

<ASIN:3540403442>

<ASIN:0387252827>

<ASIN:0471462349>

<ASIN:0387970401>