Codebreaking in Everyday Life

John D Barrow FRS,
Gresham Professor of Geometry

12/01/2010

Today I want to talk to you about some aspects of codes and code breaking which might not be familiar to you.  Codes of course seem to exert extraordinary fascination upon people and with books like the Da Vinci Code you can see that the whole idea of codes has become some sort of iconic symbol of attention and sinister conspiracy.  But all of us encounter codes in our everyday lives on a rather more mundane but mathematically much more interesting level. 

To get a feel for some of the numbers that we are going to look at in other circumstances, suppose you have a bike lock that has got a four-digit code - how many combinations are you looking at?  If it is zero to nine, you have got 10 options on each, so there are 10 x 10 x 10 x 10, which is 10,000 possible combinations.  If you were to search through all those combinations at a rate of one a second, it would take you around 2.75 hours to try them all, so, on average, you might expect to break this code in about half of that time. 

More sophisticated codes, of the sort that are used for diplomatic and military purposes, have a different type of structure.  They are usually based upon the creation of an operation in which you encrypt a message, and that operation has a particular property that sometimes mathematicians call a "trap door" function or a "trap door" operation.  A trap door has a rather simple property: it is very easy to fall through it in one direction, and quite difficult to clamber back in the other direction.  This is what you want for an encoding operation: it should be relatively simply to encrypt and encode your message, but difficult to go back in the opposite direction. 

There are many mathematical operations which have this property, but if you started with your message X, it could be something like taking the inverse cosine of X and then raising it to the power 1.3 and then subjecting it to taking its logarithm and then taking the Bessel function value of that answer.  Then you would have got a horribly complicated operation to invert and go backwards, but it is relatively simple for a calculator or a computer to go in one direction.

But most significant codes, the sorts that are used to make your credit card information secure on Amazon or other shopping sites, is based around an operation that is really seemingly rather simple.  It takes two enormous prime numbers, and multiplies them together to make an even bigger composite number.  This is something, in principle, that a computer or a calculator can do in a fraction of a second, but to factorise a given composite number into its two prime factors, if this number is 50 or 100 digits long, is something that could take the fastest computer on Earth thousands of years to accomplish.  So the point of these types of commercial codes is that they are not unbreakable in principle, but they are unbreakable in practice; they require too much processing time in order for the inverse operation to be completed.

If somebody in the world of pure mathematics were today to discover some new algorithm, some new property of prime numbers, which would allow large composites to be decomposed into their prime factors very quickly, the world would be in serious crisis if this was made known, and perhaps in even bigger crisis if it was not made known but surreptitiously used, because all the world's diplomatic and military and commercial codes would be compromised.  We don't think that has happened, but, on the other hand, would we know if it had?

It was a British number theorist, Cox, who discovered this type of encryption process - there are other more sophisticated ingredients to it - in the early 1970s.  He was working for GCHQ at the time, and there is a great story about his discovery of this simple process.  He had left the doors of GCHQ one evening after work, and the rules are that you are not allowed to talk about, write down, or in any other way record anything you think about code breaking and codes while you are off the GCHQ premises, so when he got home to his digs, he had this idea of a new type of encryption process.  He was so excited about it but he knew he could not write anything down about it - he was not allowed to do that - and he did not want to go to sleep because he thought that he would wake up in the morning and have forgotten it.  So he stayed awake all night and left at one minute to six to get to the gates of GCHQ the moment they opened, and then wrote down his new procedure.  It was kept secret.  Many years later, it was discovered again by Israeli mathematicians and publicised.  But had it been patented, as it were, at that time by GCHQ, the UK would have had a worldwide patent on all encryption processes - all credit card encryption operations.

So this is an area where pure mathematics in its purest sense, number theory, is very much part and parcel of the everyday world. But I am not, in this lecture, going to talk about that type of high level code making and code breaking, although I may return to it in another lecture.  I want to talk today about something that is seemingly much more mundane, and it is the use of what we might call codes for identifying people and places and guaranteeing the integrity of particular transactions and operations against simple errors, mistakes, as well as against people with nefarious aims.

I would like to begin with the postcode system, whereby the country is divided into various postal zones, which are labelled by letters.  As I am sure you are aware, 2009 was the 50th anniversary of the postcode.  This was not something that seemed to be greatly publicised, but 1959 was the invention of the postcode.  The first letter sent through a postcode in the UK was in Norwich fifty years ago and there were a few letter stamps that celebrated this last year, which just goes to show how interesting the world of postcodes can be?

An interesting question to ask about postcodes comes when we consider that we are using numbers and letters, so we are familiar with the idea that we are often just asked to write my house number and my postcode.  In this way, your postcode can almost identify you.  With the house number and the postcode, then things can always get back to you.  The question then is, are there really enough postcodes?  How many postcodes are there?  How many are there of these labels that governments and organisations want to create?

We here need to first ask what the pattern of the postcode is?  For the UK it is: letter, letter, number - number, letter, letter.  So, where I grew up, it was HA0 4SJ.  How many are there with this pattern?

There are 26 letters, and they are all independently chosen, which means that the letter-letter-number number-letter-letter system gives the following possible options: 26 x 26 x 10 x10 x 26 x 26.  In practice, the letters are not chosen completely arbitrarily.  So, in Cambridge, it is CB, in order to give you some information about Cambridge.  But it did not have to be, if you needed more alternatives.  If you add up 26 x 10 x 10 x26 x 26 you have got just over 45.5 million permutations.  What is the UK population?  It is about 60.5 million, when I last counted.  But what really matters is how many households are there, which comes out at about 26.25 million households.  By 2020, supposedly, there is going to be about 28.5 million.  You can see from this that there are not enough postcodes to have one each, but there is easily enough to have one per household with this type of formula.  But if you wanted to have a postcode system that was worldwide, you would need to add another letter or substitute one of the numbers for a letter.

The nearest that we have to a personal identity number if we are an adult, over 16 - a thing that could, in principle, coordinate, if it were legally permitted, every piece of official information about us, whether it is in the tax authorities or the NHS or the electoral roll or whatever - is our National Insurance number.

How many of those are there?  The pattern again for almost all them is: letter, letter, and then six numbers, and then another letter.  So if you look at the number of possibilities there, you are looking at 26x26x10x10x10x10x10x10x26, which is a little more than 17.5 billion.  The population of the world at the moment is not quite 6.7 billion.  So there is enough UK National Insurance numbers for twice the world's population, nearly three times the world's population, so they are insuring against a very large number of possibilities that are required in the future.  So you get a feel here for the difference it really makes in using letters rather than numbers.

I want to now gradually move towards looking at links between people and how we might try and understand these enormous numbers of people that we have, both in the UK and in the world, the extent to which they are linked together in particular ways. 

The most interesting original experiment of this sort is by a very famous name indeed.  Stanley Milgram was an experimental psychologist, and a genius in one particular respect: for conceiving and designing experiments.  I am sure people who studied Psychology even at school, and certainly at university, will know of something that is called the Milgram Experiment, or the Milgram Obedience Experiment.  This is one of the most famous laboratory experiments ever conceived.  You would not be allowed to perform it today, as ethics restrictions would not allow it to be performed.  But let me tell you about his famous experiment before we look at his other experiment.

The famous Obedience Experiment, was motivated by his hearing and watching the events surrounding the Eichmann trial in the very early 1960s, and thinking about the problems surrounding guilt and responsibility and the sort of evidence that was being heard at the trail, of people saying that they were only following orders and this is why they sent people to concentration camps and so on.  He conceived of an experiment in which he wished to understand how people respond when they are asked to do things from some authoritarian source; the way in which they will suspend their own ethical principles because the feel they must obey what they are being told. 

His experiment used a couple of actors, and it recruited people by advertisement.  They were then told they were going to help with an experiment about teaching and learning.  The teaching and learning experiment was that pairs of words were going to be given to a subject, the learner, and they were going to answer a question about were they were related or some such thing.  If they got the answer correct, that is all very nice - they got a reward of some kind; but if they got it wrong, they got an electric shock.  He also would always throw in a little comment along the lines that one must be a little careful because this particular subject has heart problems.  As the number of errors made by the subject increased, so the electric shock was increased, so the teacher, as he was called, the person who had to administer the shock, was told that the next one is going to be 200 volts, and the next one would go all the way up to 450 volts, and so on.  As this s going on, the actor was screaming from next door as the voltage goes high, and then eventually would, in many cases, simulate death or unconsciousness.

So when he carried out an investigation beforehand, asking Psychology students how they thought such an experiment would pan out, the result was fairly uniform.  People felt that perhaps 1% of people that you used as these teachers to give the instruction to administer the shock might do this, but they felt that almost everybody would refuse to do it.

But his result was very alarming: he found that 65% of people who he engaged following the orders and administered what they thought was the shock all the way up to unconsciousness and apparent death of the subjects.  So they were so taken over by the authoritarian structure of the experiment and the man in the white coat telling them to keep pressing the button and that they could not stop the experiment.

This was Milgram's famous experiment, which would not be allowed today.  But this is only a digression.  His other experiment, also beautifully conceived, was he wanted to get a feeling for the connectivity of society in the USA.  He had the idea of creating lots of letters which would be rather incompletely addressed, to a stockbroker in Boston.  All you had on the envelope was a name and the city, and it might have some company name like Such-and-Such Stockbroking.  He decided that he would put all these letters into the mail system, give them to people at random, in a part of the country which socially was as far apart, at the opposite pole, to Boston - Omaha, Nebraska and Wichita, Kansas.  He distributes these letters at around 400 at a time or so, each with the instruction at each stage for the letter to "Get closer to its destination".  So if somebody knew a stockbroker, they would probably post it to them.  If they knew someone in the Boston area, they would post it on to there, hoping that the next person might know a bit better the intended destination.  When people did post it on, they were asked to send a card back to say they had done it and where they had sent it.  They found through this that, amazingly, about a fifth of the letters that he started in this system in Nebraska found their way, ultimately, to the intended recipient in Boston. 

This was the beginning of an understanding of what became known as social networking and the so-called 'small world' structure of networks.  Milgram himself created this terminology of the so-called six degrees of separation, because, on average, it took only about six re-postings of his letters for the successful mailings to reach their destination.  So this then served as the first example of the way in which networks of friends and acquaintances bound and linked people together.  So even though the population was in tens of millions, it was possible for a connection to be made between these highly disparate social populations in this very small number of steps.

So this great insight of Milgram way back in the 1960s has, in the last 15 years, become something of a major study.  So whether you are studying the structure of the brain, the way it works, you find it has this type of small world network structure; whether you are trying to understand social networks or networks of influential businessmen and so forth.

It is not a very accurate way to do the calculation, but you can get a feel for why this is the case if we suppose we assume that each of us know 100 people, and let us assume that each of those people knows another 100 people.  Then if we go even one step beyond our own circle of 100 friends, we have connections to 100x100 people, which is 10,000 people.  What we are neglecting here is all the overlaps between those friends, but you can take care of that if you do a little more mathematics.

If we take N steps away, where the first step are your friends, and then the next step are the friends of the friends, and so on, you are linked to 10 to the power 2N + 2 people: 102(N+1).

We have already seen that the world population is 6.65 billion.  That is 10 to the power 9.8.  So 102(N+1) is bigger than the world population, when 2N + 2 is bigger than 9.8.  So that is when N exceeds 4, which is just four steps away.  Therefore, under this model, you have got more acquaintances than the entire population of the world in only four steps.

When you take into account all those double-countings where, after three steps, you start running into people that you already counted in the first step, this changes the calculation a little bit, but not by much: the 4 simply becomes 6.

This is an interesting situation because, naïvely, people think of links whereby, if you want to make a link between yourself and the Pope, one thinks of a link being made just along all the people in between along a straight line.  But what is being investigated here is the fact that the best type of network structures have random links, which do not mean that you just have to go round the outside to link people up, but you can jump across.

When people think about this sort of thing, they tend to pick an example that is odd or unusual.  If I ask you "How many steps are you away from meeting the Pope?" say, you will probably find it is rather small.  For instance, you might know the chap at your local Italian pizza house, whose mother will have met the Bishop in Rome, who will be on nodding terms with the Pope.  Another example might be, "How many steps are you away from meeting the Queen?"   Well, you have met me, and I have met the Queen, so you are really very close!

If you want to find the counter-examples, it is not famous people.  The counter-example is "How many steps are you away from some Bushman in the Amazon jungle?", because you will not be very closely linked to people of that sort.  This is because they are the people that have small amounts of connectivity.  In effect of you are really rather closely connected, you will find, if you think about it, to very famous people, the "princes", because they have a lot of connections, but you are really rather weakly connected to people who live in the middle of nowhere, that do not have a lot of social links, the "paupers".  So they are the outliers in this process.

The other thing that you appreciate from this is that friends of friends of friends, or even friends of friends of friends, are very important, just as important as friends.  You see, the thing about your friends is that they are a lot like you.  They know all the same sorts of people as you, and they do a lot of the things that you do.  So if you are a business person or somebody else interested in having a very broad range of connections, having a lot of input and advice from diverse sources, if you just focus on your friends and immediate acquaintances, you will not produce a very large pool of diverse advice.  You will be talking to people who are a lot like you, with the same sort of contacts.  It might be university professors and so forth.  But if you go one or two steps further downstream, you start to come into contact with those rather loose acquaintances who are magicians and astronauts and footballers or whatever.  Because this group of people are very different, they offer you a quite different spectrum of acquaintances and experiences and information.

There was a famous example in the world of mathematics which preceded, almost by experiment, a lot of this study.  There was a very great mathematician, in some ways perhaps the greatest of the 20thCentury, called Paul Erdös, who died just a few years ago.  He was the most prolific mathematician probably of all time.  Only Euler is more prolific. 

Erdös was Hungarian and he was the so-called Extraordinary Professor of the Hungarian Academy, who paid him to do mathematics.  He had no home: all his possessions were just two suitcases, and he travelled the world with his elderly mother, and he would stay with all his collaborators and friends or in hotels, just doing mathematics.  He wrote, probably, on average, about thirty research papers a year, all extraordinarily good, which varied from the proof of the prime number theorem to many other challenge problems.  He had a skill for determining the difficulty of a problem, and he would offer cash prizes for the solution of the problems which he posed.  They were very finely judged.  Some may be $10 problems, some may be $10,000 problems, but he rarely ever judged the difficulty wrongly.  In this way, he spurred on research in number theory, and he funded the prizes from the prizes that he was awarded, so he used that prize money to fund these prizes of his own creation. 

He had so many collaborators that there are all these stories that, you know, he would arrive in town and by the time he had left the railway station, he would had already written a paper with the porter or something.  So sometimes, at conferences, there will be this unusual structure in a hotel, rather like in a chess match, where there would be maybe twenty of his collaborators from different parts of the world that would seat themselves at different desks or tables, and then he would move from one to the other, spending maybe fifteen minutes trying to attack the next part of a problem, and then he would move on to the next collaborator, and go on around, so it was like a simultaneous chess tournament, with him contributing to each collaboration and then coming round again at the end.

Because of this huge number of collaborators and publications, something called the Erdös number was created by mathematicians.  If you had written a paper with Erdös, you had an Erdös number of one.  If you had written a paper with somebody who had themselves written a paper with Erdös, you had an Erdös number of two, and so on.  So Robin Wilson, my predecessor, has an Erdös number of one, since he once wrote a paper with Erdös, and there is a huge number of mathematicians in the world with Erdös number one, and almost everybody, in the whole community, has an Erdös number of around five or less, so everybody is connected to Erdös through collaboration.

You can see that it is just like the small-world situation, the six degrees of separation, when you are measuring the distance that you are in such a network.  One way of measuring this distance is to measure the number of nodes, the number of places where there is some splitting, extra friends as it were, and then the number of links or friends per node.  So the average distance that you would expect to go in a complicated network to go from any two points would be the ratio of the logarithm of the number of nodes divided by the logarithm of the number of links or friends per node:

        Average Dist = (ln N / ln K) = 5.9
        (Where N = total nodes and K = friends per node).
        And K=30 and N = 108.8 = 10% x world population

So, for this case, it is about 5.9.  So even with 30 friends per node and the population of the world, as it were, you have got 10% or so of the world's population included.  So people had understood this type of structure experimentally in other situations.

That just gives you a little flavour of some of these consequences of numbers like the number of people in the population, the number of people in the world, and what you have to then think about if you want to have a system that identifies them or distinguishes them.  But I now want to move now to looking at some of these coding systems.

A simple one that you will certainly have been involved in, unwittingly, is called the Soundex Phonetic System, and it is a way that is used in business and booking systems to try to avoid getting your name wrong in a catastrophic way because of spelling errors or other mistakes.  Most of the things that we are going to look at now are going to be forms of encoding information that make them robust against all sorts of different types of errors and mistakes, so that your booking on some airline does not end up being voided because somebody types in one letter incorrectly in your name or your address.

This was invented back in 1918 to help people who were searching and using the census system in the US.  People who were searching for their ancestors from Sweden in the US might be looking for an Erikson, and as you can imagine, there are all sorts of ways you would end up spelling Erikson, and you do not want to end up with the ex-England football manager instead of your grandfather, so you want to have a system that makes sure that you see all the variants that might arise by mistake. 

This system is interesting.  You take a name, so a christian name and a surname, such as "John Barrow".  The first thing you do is to keep the first letters of the names. Then you delete all the vowels plus H, Y, and W, so you kill off these letters, and for the rest of the letters that remain, these consonants, you give a value 1 to B, F, P and V; 2 to C, G, J, K, Q, S, X and Z; D and T you give 3; to L you give a 4; M and N get 5; and R is 6:

        Keep the first letter of the name
        Delete A, E, I, O, U, H, V, W
        Assign numbers to the rest of the letters
        B, F, P, V = 1
        C, G, J, K, Q, S, X, Z = 2
        D, T = 3
        l = 4
        M, N = 5
        R = 6

If you have got two letters with the same number next to each other in the original name, so if you are "Allan" with two 'L's, you only keep one of them, and you keep a number for that 'L'.  You only keep the first four characters, so you are not going to keep more than four.  If the name ends up with fewer than four, then  you fill it up to four just by adding zeros. 

So, in the case of my name, we get rid of the 'O' and the 'H', so you have just got JN in my first name.  In the surname you keep the B, you lose the A, you have got double R, you only keep one of those, you lose the O, and you lose the W, and you end up with JNBR.  The N goes to 5 and R goes to 6, and you fill out with pairs of zeros the other spaces you need to occupy, so you have got J500 B600. 

The advantage of this system, if you try it on a few others, you will see that names like Smith and Smyth end up with the same designation.  To use the name we mentioned before, we will see that all of Ericson, Erickson, Eriksen and Erikson, all end up encoded as E6225.  So you store the information with that number.  If you pull it up when you are searching for a name, you see all these variant Erikson spellings, so you have a way of picking and choosing between them; whereas, if the computer just stored one of the spellings, you would not be aware of all the other possibilities.

So this is an example of a compression of information; you are throwing some information away, you are encoding the information that remains, not to keep it secret, but in order to make different things appear the same, because people spell things differently and they make mistakes and so forth.

This robustness against making mistakes is all around us in a series of encodings that are known as check digit codes.  You see them on all sorts of cards and tickets and so forth, and you will have many of them in your pocket at the moment - by the end of this lecture, you will be aghast at what you are carrying around with you.  The idea is, first of all, to guard against simple transcription errors.  So, if the person on the other end of the phone in Timbuktu who is dealing with your bank account over the phone, and the line is rather crackly and perhaps they do not really speak much English, you want to have protection against them just writing down the wrong amount.  So when you say your account number, what insurance do you have that they will not make a transcription error?

There are certain sorts of fraud which are rather naïve.  Suppose, at home, that you had a bank note printing system, and you were just running off thousands of bank notes, and you have thought that you would just add in some serial numbers.  Well, not any old organisation of the right number of digits is a valid serial number for a bank note, so there is an internal check digit code which will be used to validate some of those numbers. 

So passports, credit cards, and so forth, what we are worried about are these sorts of typing errors where it is maybe just the mistake of making a one-digit mistake or adding an extra number of flipping them around and so forth.  Can you devise a system which is efficient enough to recognise almost all of those sorts of errors and stop the transaction going any further?

To begin with a simple worked example, we can look at airline tickets.  An example ticket number might be: 4851913640.  There is a check digit system in operation here because there is another little digit, just beyond the main number, which is a 3.  This comes from the fact that if you divide that ticket number by 7, it does not go exactly, because you end up with a 10 at the end, and there is a remainder of 3.  So the check digit is the remainder after you divide the ticket number by 7, which is why the 3 appears after our example.  So if somebody was to write this down incorrectly and flip some numbers around in the code, when it was divided by 7, the remainder would not be equal to the check digit, in this case 3, and the number would be invalid.  So there is a simple internal consistency check that this is a valid ticket number.

This type of structure is developed in all sorts of different ways for different types of devices to guard against typical transcription errors.  You might remember the Victor Meldrew story from One Foot in the Grave, where a simple transposition created such a disaster for him, that instead of ordering one item of catalogue object number 250, he ended up ordering 250 items of catalogue object number 1, which was the garden gnome, so he ended up with an awful lot of garden gnomes. 

Research that people do on documents shows that these are the most common type of errors that you make:

        a by b                      79%
        ab by ba                  10%
        abc by cba               1%
        aa by bb                  0.5%
        a0 by 1a (a=2,3,..)   0.5%
        aca by bcb               0.3%

The first is of just replacing one number or one letter by a different letter, and that occurs nearly 80% of the time.  The second is a matter of inversion, whereby instead of writing 2 letters, you write the inversions, which occurs about 10% of the time.  Doing it with three digits is about 1% of the time.  Errors with repeated doubles or letters and numbers, are all a fraction of a percent.  So you can see that, in practice, we certain sorts of errors.

One example where this is rather crucial that you get things right is in banking and bank accounts.  If you ever have to do any transactions, sending or receiving money from abroad, sending a cheque to your children in Canada or something, you have probably noticed that in recent years there are draconian requirements of international banking codes that have to be given in addition to your sort code and bank account number in order to receive money.  One of these, which is sufficient, the so-called IBAN, an international bank code.

Your IBAN number, which will probably sit on the top of your bank statement, will be of this pattern:

                GB82 WEST 1234 5698 7654 32

What is the pattern here?  The first bit, the GB, is just a country code, which here stands for Great Britain.  The next one, 82, is the cheque number.  Then, in this case here, the next four letters tell you the bank - this is Westminster.  An odd thing about all banking electronic codes is that they still use all the code names of the banks that no longer exist.  So if you are sending money to Egg Bank, it is coded as Midland or something like that.  So these old code numbers live on.  Then you get your sort code, which is here 123456, and then you get an account number, which is here 98765432.

What is done with this number by the bank's computers is really rather elaborate.  First of all, it takes the four characters at the beginning and moves them to the end.  Then it takes all the letters in the bank name and the GB, and converts them into numbers.  So wherever you see an 'A', it's replaced by '10', wherever you see a 'B', by '11', and so forth, all the way up to Z if necessary (it is replaced by '35').  So you have then got a long string of numbers which is interpreted just as a single decimal, a single number.  This number is then divided by 97.  In order for the number to be a valid IBAN, the remainder has to be 1.

This is what mathematicians call a modular arithmetic.  97 is chosen so that, if you consider all the types of error and transposition that you could make in mis-writing the number, the largest fraction that is practical gets caught by this algorithm.

Here is how it works with this invented one we chose earlier:

        GB82 WEST 1234 5698 7654 32
        WEST 1234 5698 7654 32 GB82
        WEST = 32142829
                     3214282912345698765432161182
        = 1 mod 97

So we first of all, we moved the group of two letters and two numbers at the front, to the end.  We then converted the four letters at the front and the two numbers now near the end into numbers, so W goes to 32, E is 14, S is 28 and T is 29, and so on, and so we have got a single number.  If you divide it by 97, there is a remainder of 1.  So this is a valid IBAN number.

So if your banker had made a transcription error here, except for probably about 1% of unusual transcriptions, where there are certain transpositions that cancel each other out, it would identify that an error had been made and that this was not a valid international banking number.

Similarly, if somebody wants to invent a fictitious bank account for some nefarious purpose, the number they invent has got to meet this rather strict formula.

Credit cards use a rather similar idea, a similar encryption, but it is a little different.  We are gradually working towards an understanding of what is the general structure of all these things.  So probably on your credit card, you may have a 12 or a 16 digit form.  Here's a 16 digit form that I have just invented:

        4000 1234 5678 9314

What we do is that, first of all, we adopt a test that has become known as the Luhn test because it was created by Peter Luhn when he worked for IBM in the 1950s.  So he was asked to invent a secure check digit encryption for banking numbers at that time, and this is what he came up with, and it has remained pretty much an industry standard ever since. 

You work from the left to the right - you take every other digit, the odd-placed ones: the first, the third, the fifth, and so on.  Then you double each of these odd-placed numbers.  If the result you get is larger than 9, then you add the two digits together.  So if you got 14, you just add the two digits together to get 5.

We can do this with our sample number:

        Starting number:                                4000 1234 5678 9314
        Odd-placed numbers:                         4 0 1 3 5 7 9 1
        Double those numbers:                      8 0 2 6 10 14 18 2
        Add the digits together when over 9:   8 0 2 6 1 5 9 2

Once you have done this, what you do is to add those digits together, and add the other digits which were in the even-numbered positions:

        8 + 0 + 2 + 6 + 1 + 5 + 9 + 6   =  33
        33  +   0 + 0 + 2 + 4 + 6 + 8 + 3 + 4  =  60

What you are doing here is creating a weighted sum.  You are adding the even-positioned digits to some multiplier times the odd position digits.  For your credit card number to be valid, this number must be divisible by ten.  So if you are in the business of creating fake credit cards this is the constraint that you have to meet.  So, for example, the number 4000 1234 5678 9010 would fail as when you out it through the sum of the Luhn test, it comes out as 57 and is therefore not divisible by 10.

So this little algorithm catches every single digit mistake, so every mistyping of a single number, and it contains almost every swapping of numbers which are next door to each other being erroneously changed.  The number swap that it does not pick up is 09 / 90 - so when you come to make the addition, it doesn't make any difference.  So you can now check your credit cards to make sure that they are all valid!

The next example of this sort that you see all the time is something that is known as the UPC, or the Universal Product Code.  So everything around us has these on - from your television to your newspaper - they are the bar-codes whereby somebody has to scan the UPC to put it into the till computer. Pretty much every retail product is encoded in this way, and the pattern of the encoding of the bars is created in a cunning way, so that it does not matter which direction the laser scanner looks over it - it has a certain symmetry.  There are guard bars, double bars, at each end, to tell the machine that it is about to start reading, and the pattern that you have is divided up into different types of bar, and the thickness of the bars are just telling you the numbers.  Sometimes the numbers appear as well.  Here is a typical example:

You have a number like 6 on the outside, then you have a little group of five numbers, another group of five, and then another single number on the outside.  But what is this code telling you?

The first number is telling you something about the product, and there is a set of little catalogue values.  Some numbers, like 6 for example, as well as 0, 1, 7 and 9, are used for miscellaneous things - they can be used for anything; whereas numbers like 2 are used for food that is sold by weight, such as at the greengrocers or something like that.  4 is if something is on sale, so the price is reduced.  So there are some legal requirements about sale items, that they have to have been advertised or on sale at a higher price for some period.  Then there are things that have coupons and special offers.  That is the first number.

The next number is telling you something about the manufacturer.  Then there follows a lot of information about the size, the colour, the model number.  This last number is a check digit.  This is created by a combination of the others and it is to tell you whether the other numbers are correct or not.

I picked up an example from an eraser pen I had at home and its UPC code was as follows:

        3  474370  01631  7

What we do with this one is a bit like Luhn, we add together the digits which are in the odd-numbered positions, we get 17, and for the product code, you then multiply by 3, and then add the other digits which are in the even-numbered positions.  In our example this comes out in the following way:

        Add digits in odd positions: 3 + 7 + 3 + 0 + 1 + 3 = 17
        Multiply by 3: 3 ´ 17 = 51
        Add digits in even positions: 51 + 4 + 4 +7 + 0 + 6 + 1  =  73
        Divide by 10: check digit is 10 minus the remainder = 10 - 3 = 7

17 multiplied by 3 is 51.  We then add the even-positioned digits, and you get 73.  Divide by 10 and the check digit is 10 minus the remainder.  The remainder is 3, so take that from 10 and you get 7.  Another way of saying that is: the check digit is the number that you need to add to your answer to make it divisible by 10.  So in this case, you have got to add 7, and indeed, there is a 7 there.  So if you made a mistake anywhere here, this would show it up.

Again this uses some modular arithmetic, in a sense, but it is dividing now by 10.  This is different than the 97 that was used in the IBANs sum before.

We will do two more cases of this type, and the first one should be rather familiar to you as it is the one for books, the ISBN number.  The old ISBN used 10 numbers but the new one uses 13.  Here is an example of the new ISBN:

It has a similar type of structure to the UPC code, as it is going to be bar-code read as well.  You have got a first number, on the left, 9, which tells you something about the region, then there are numbers which tell you about the publishing group, the publisher, the title of the book etc.  Then the last digit, at the end, is the check digit. 

The curiosity about the old ISBN is that sometimes you find the letter X on the end.  So what happens here is that you end up carrying the same operation out: you multiply each digit in the number by its position from the right.  So the one is first from the right, the second, the third and so on, if you multiply them by 1, 2, 3, 4, add it all together, and divide by 11.  So it must be divisible by 11 to be a valid ISBN.  But divided by 11 means that you could have a remainder of 10, and because of that, you sometimes see an X, a Roman 10, being used to denote the 10.  So, for the ISBN, 0-19-280569-X, if we divide this by 10, the sum is 199 + X, and so, if X was equal to 10, it would be 209, which is divisible by 11.

This is a bit laborious and a few years ago most books then changed to a different system, where they use 13 numbers, but even-numbered digits in the number are multiplied by 3, but the odd ones were not.  So it is like the UPC, multiply by 3 on the even digits - UPC multiply by 3 on the odd ones - and the check digit is just the number that you need to make the answer divisible by 10.  So it is very much like the UPC, but it operates on the even numbers instead of the odd numbers.

I will do one more example and then tell you what the general pattern really is looking like here mathematically.  Mobile phones have IMEI numbers; the so-called International Mobile Equipment Identity number.  If somebody steals your phone or you lose it, this is what you have to cancel.  If you look inside the phone, it is the long number printed below and represented in a barcode.  To change this number on a phone is a criminal offence.  It has a structure of 14 digits plus a check digit.

              49 015420323751  8

To arrive at the check digit right at the end, you take every other number and you double it.  We have seen this before: double the 9, double the 1, double the 4, double the 0, double the 7, and you get 14.  As before, if you get 2 digits, add them together, so 18 turns into 9, 14 into 5.  And then you add everything together.  So the other digits were left alone, add everything together and you get 52, and the check digit is going to be the extra number that you need to make that sum divisible by 10.  So 52 + 8 is going to be divisible by 10, so that is the final number that is on your IMEI.

This is probably enough of these examples, so the last thing I just want to show you is, mathematically, what is going on here in these structures.  So you get the general idea, that you are surrounded not just by numbers and codes, but they all contain these internal checking devices to make sure that they are not susceptible to silly and simple mistakes.

What happens here is that there is some code number, which I will call A1, A2, A3, A4, up to AN - it has got N digits in it.  So this might be your mobile phone number.  If it starts with letters in it, you carry out some operation to turn the letters into numbers.  We have seen, what you do with that number is to treat it rather like a vector and form a dot product with another list of numbers, which are what we called the weights.  So the even numbers, we might leave alone; the odd numbers, we double.  So what that is like saying is the first number and third number and the fifth number, we leave alone, so the weights there are 1, but the ones in between, the weights are 2 - we are going to double them.  So we take our code number, and we form a dot product with this vector of weights.  What that dot product means is that it is A1 x W1 + A2 x W2 + A3 x W3, and so on, all the way up to AN x WN.  So, if you have done vectors at school or college, this is a scale of product, or you can think of matrix language - this is a row times a column vector, and the answer you get, when you multiply all those things together and add them up, is just a number.  What happened was that we then, say, subtracted that answer away from some other number, and we divided it by R or some other, 10 or 97 or something like that, and this was the check digit.

        C = r - (a1 ,a2 ,a3 ,...an)×(w1,w2,w3 ,...wn) = r - a×w (mod r)

So the general pattern of the check digit structure is to start with a code number, introduce some collection of weights, choose which numbers in your code number you are going to operate on, and then divide the answer by some number - 10 or 97 or something else - and the check digit is going to be the remainder when you take that away from 10, say, or 97.

Here are the examples we looked at:

        UPC : n = 12, w = (3,1,3,1...),  r= 10
        EAN-8: n = 7, w = (3,1,3,1...),  r= 10
        Airline: n = 10, w = (1,1,1,1...), r= 7
        ISBN-10: n = 9, w = (10,9,8,7...,2,1),  r= 11 and X =10
        ISBN-13 and EAN-13: n = 12, w = (1,3,1,3...),  r = 10

The Universal Product Code had 12 numbers.  The weights were 3, 1, 3, 1, 3, 1, so you did nothing to the even numbers, but you multiplied the odds by 3, and the final answer had to be divisible by 10. 

The airline one had 10 digits.  There were no weights, so everything was just the same - we just added everything together (the weights were all 1), and it had to be divisible by 7.

ISBN had 9 numbers, in the old one, plus the check digit - and the weights went backwards - 10, 9, 8, 7...4, 3, 2, 1 - divide by 11, and we used X for the number 10. 

The new ISBN and the Product Code, you had 12 digits.  This time, the weights were not 3, 1, 3, 1.  They were 1, 3, 1, 3, 1, 3.  You multiply this by A, and the answer had to be divisible by 10.

This is a general type of structure for producing robust codes.  The only one that is really qualitatively different, that uses more sophisticated mathematics, so uses a different algebraic structure than just multiplying these things together, is that on German bank notes.  It uses a non-commutative arithmetic, not ordinary arithmetic, developed by Gauss, in order to produce their check digit codes.

Well, you will have probably got extremely worried by this talk, but the whole of your life is surrounded by modular arithmetic and codes and numbers.  Maths really is everywhere!

© John D. Barrow, 12 January 2010