Testing to see if a number is a prime or not is the basis of many encryption and security methods. It has long been assumed that there is no fast way, i.e no polynomial time method, to determine if a number is prime, but now we know different.

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

Contents

1. What Is Computable?
2. Finite State Machines
3. What is a Turing Machine? 
4. Computational Complexity
5. Non-computable numbers
6. The Transfinite
7. Axiom Of Choice
8. Lambda Calculus
9. Grammar and Torture
10. Reverse Polish Notation - RPN
11. Introduction to Boolean Logic
12. Confronting The Unprovable - Gödel And All That
13. The Programmer's Guide to Fractals
14. The Programmer's Guide to Chaos*
15. Prime Numbers And Primality Testing
16. Cellular Automata - The How and Why
17. Information Theory
18. Coding Theory
19. Kolmogorov Complexity

*To be revised

It is lesson to us all that a classic problem that was long thought not to have a polynomial solution does indeed have one. Given that we rely on some of these problems to keep our secrets safe, this is a change in perspective.

Forget the excitement and mystery of Fermat’s last theorem or the lure of the Riemann hypothesis, the result announced in  2002 by Agrawal, Kayal, and Saxena, of the Indian Institute of Technology in Kanpur solves one of the oldest and most important problems in pure mathematics – how to test if a number is prime or not.

The three people who solved the primality testing  problem in 2002.

They simultaneously sent a wave of amazement through the mathematical world and a shudder through the world of spys and spooks.

The reason for the amazement is that solution to the problem doesn’t use brand-new advanced methods but a fresh approach to the problem. The reason for the shudder is that the whole of our digital security, codes, signatures and certificates, depends on the pure mathematics at the heart of the primality problem.

Factoring and codes

Before going on to explain the new ideas it helps to put the whole thing in context of why it is of practical importance in computing.

The entire security of the Internet and much desktop computing is based on the PKI, or Public Key Infrastructure. This allows two users, or machines, who have never met before to establish secure communication without any real possibility that a third party can eavesdrop.

The basis of this method is the use of two numeric keys - a public key which can be used to code a message which can only be read with the use of another key, the private key. This is now such a commonplace that it is possible to miss how odd the idea is.

You have a mathematical algorithm based on a key that mixes up data that can only be undone easily if you have another key.

All of this seems very abstract and explaining it in all its detail would take some time, but there are simpler examples that illustrate the basis of the PKI.

For example, suppose Bob wants to send the serial number of a luggage locker to Alice, then one simple way to do it is to send a number which is the product of the locker number and another number – the key.

We are assuming that the locker number and the key are prime numbers which, in the locker's case is unlikely. There are ways around the problem for example Bob could add a message to Alice that his locker number was 145 less than the smallest factor. 

Bob might use a prime key picked at random but smaller than 10,000 to encode the locker number and send Alice:

     137703491

Now all you have to do to crack Bob’s code is to find two prime numbers which multiply to give 137703491.

You might think that this was easy but the only way to do it is to start off with 2 and work your way through all the possibilities until you find something that divides it exactly.

Of course there are shortcuts.

For example once you have checked that it isn’t divisible by 2 you don’t have to check 4, 6, 8 and so on, but there is still enough checking to keep you busy and more importantly the work involved increases in an unreasonably demanding manner as the size of the number goes up.

So factoring 143, a three-digit number, is easy enough (11 times13) but factoring 137703491, a nine-digit number, is far more than three times more difficult. What this means is that no matter how good computers get at factoring Bob can just pick a bigger pair of numbers to multiply together.

In the jargon multiplication is a “one-way function” because undoing it is harder than doing it.

How does Bob get the information out?

Easy - since he chose the key he knows that it is 7919 and if you also know this you can get the locker number back by simple division:

      137703491/7919 

gives you the locker key. 

If you find this example unconvincing tell me what two numbers multiply together to give:

     7621615238978741781241003

(Answer at the end of the article) 

Public key cryptography is based on similar, but slightly more involved methods, for factoring a number but it is worth knowing that many schemes would be easy to break if anyone could find an easy way of factoring large integers.