Fermat's Last Theorem (23 page)

A truel is similar to a duel, except there are three participants rather than two. One morning Mr Black, Mr Grey and Mr White decide to resolve a conflict by truelling with pistols until only one of them survives. Mr Black is the worst shot, hitting his target on average only one time in three. Mr Grey is a better shot hitting his target two times out of three. Mr White is the best shot hitting his target every time. To make the truel fairer Mr Black is allowed to shoot first, followed by Mr Grey (if he is still alive), followed by Mr White (if he is still alive), and round again until only one of them is alive. The question is this: Where should Mr Black aim his first shot? You might like to make a guess based on intuition, or better still based on game theory. The answer is discussed in
Appendix 9
.

Even more influential in wartime than game theory is the mathematics of code breaking. During the Second World War the Allies realised that in theory mathematical logic could be used to unscramble German messages, if only the calculations could be performed quickly enough. The challenge was to find a way of automating mathematics so that a machine could perform the calculations, and the Englishman who contributed most to this code-cracking effort was Alan Turing.

In 1938 Turing returned to Cambridge having completed a stint at Princeton University. He had witnessed first-hand the turmoil caused by Gödel's theorems of undecidability and had become involved in trying to pick up the pieces of Hilbert's dream. In particular
he wanted to know if there was a way to define which questions were and were not decidable, and tried to develop a methodical way of answering this question. At the time calculating devices were primitive and effectively useless when it came to serious mathematics, and so instead Turing based his ideas on the concept of an imaginary machine which was capable of infinite computation. This hypothetical machine, which consumed infinite amounts of imaginary ticker-tape and could compute for an eternity, was all that he required to explore his abstract questions of logic. What Turing was unaware of was that his imagined mechanisation of hypothetical questions would eventually lead to a breakthrough in performing real calculations on real machines.

Despite the outbreak of war, Turing continued his research as a fellow of King's College, until on 4 September 1939 his contented life as a Cambridge don came to an abrupt end. He had been commandeered by the Government Code and Cypher School, whose task it was to unscramble the enemy's coded messages. Prior to the war the Germans had devoted considerable effort to developing a superior system of encryption, and this was a matter of grave concern to British Intelligence who had in the past been able to decipher their enemy's communications with relative ease. The HMSO's official war history
British Intelligence in the Second World War
describes the state of play in the 1930s:

By 1937 it was established that, unlike their Japanese and Italian counterparts, the German army, the German navy and probably the air force, together with other state organisations like the railways and the SS used, for all except their tactical communications, different versions of the same cypher system – the Enigma machine which had been put on the market in the 1920s but which the Germans had rendered more secure by progressive modifications. In 1937 the Government Code and Cypher School broke into the less modified and less secure model of this machine that was being used by the Germans, the Italians and the Spanish nationalist forces. But apart from this the Enigma still resisted attack, and it seemed likely that it would continue to do so.

The Enigma machine consisted of a keyboard connected to a scrambler unit. The scrambler unit contained three separate rotors and the positions of the rotors determined how each letter on the keyboard would be enciphered. What made the Enigma code so difficult to crack was the enormous number of ways in which the machine could be set up. First, the three rotors in the machine were chosen from a selection of five, and could be changed and swapped around to confuse the code-breakers. Second, each rotor could be positioned in one of twenty-six different ways. This means that the machine could be set up in over a million different ways. In addition to the permutations provided by the rotors, plugboard connections at the back of the machine could be changed by hand to provide a total of over 150 million million million possible setups. To increase security even further, the three rotors were continually changing their orientation, so that every time a letter was transmitted, the set-up for the machine, and therefore the encipherment, would change for the next letter. So typing ‘DODO' could generate the message ‘FGTB' – the ‘D' and the ‘O' are sent twice, but encoded differently each time.

Enigma machines were given to the German army, navy and air force, and were even operated by the railways and other government departments. As with all code systems used during this period, a weakness of the Enigma was that the receiver had to know the sender's Enigma setting. To maintain security the Enigma settings had to be changed on a daily basis. One way for senders to change settings regularly and keep receivers informed was to publish the daily settings in a secret code-book. The risk
with this approach was that the British might capture a U-boat and obtain the code-book with all the daily settings for the following month. The alternative approach, and the one adopted for the bulk of the war, was to transmit the daily settings in a preamble to the actual message, encoded using the previous day's settings.

When the war started, the British Cypher School was dominated by classicists and linguists. The Foreign Office soon realised that number theorists had a better chance of finding the key to cracking the German codes and, to begin with, nine of Britain's most brilliant number theorists were gathered at the Cypher School's new home at Bletchley Park, a Victorian mansion in Bletchley, Buckinghamshire. Turing had to abandon his hypothetical machines with infinite ticker-tape and endless processing time and come to terms with a practical problem with finite resources and a very real deadline.

Cryptography is an intellectual battle between the code-maker and the code-breaker. The challenge for the code-maker is to shuffle and scramble an outgoing message to the point where it would be indecipherable if intercepted by the enemy. However, there is a limit on the amount of mathematical manipulation possible because of the need to dispatch messages quickly and efficiently. The strength of the German Enigma code was that the coded message underwent several levels of encryption at very high speed. The challenge for the code-breaker was to take an intercepted message and to crack the code while the contents of the message were still relevant. A German message ordering a British ship to be destroyed had to be decoded before the ship was sunk.

Turing led a team of mathematicians who attempted to build mirror-images of the Enigma machine. Turing incorporated his pre-war abstract ideas into these devices, which could in theory methodically check all the possible Enigma machine set-ups until
the code was cracked. The British machines, over two metres tall and equally wide, employed electromechanical relays to check all the potential Enigma settings. The constant ticking of the relays led to them being nicknamed
bombes.
Despite their speed it was impossible for the bombes to check every one of the 150 million million million possible Enigma settings within a reasonable amount of time, and so Turing's team had to find ways to significantly reduce the number of permutations by gleaning whatever information they could from the sent messages.

One of the greatest breakthroughs made by the British was the realisation that the Enigma machine could never encode a letter into itself, i.e. if the sender tapped ‘R' then the machine could potentially send out any letter, depending on the settings of the machine, apart from ‘R'. This apparently innocuous fact was all that was needed to drastically reduce the time required to decipher a message. The Germans fought back by limiting the length of the messages they sent. All messages inevitably contain clues for the team of code-breakers, and the longer the message, the more clues it contains. By limiting all messages to a maximum of 250 letters, the Germans hoped to compensate for the Enigma machine's reluctance to encode a letter as itself.

In order to crack codes Turing would often try to guess keywords in messages. If he was right it would speed up enormously the cracking of the rest of the code. For example, if the code-breakers suspected that a message contained a weather report, a frequent type of coded report, then they would guess that the message contained words such as ‘fog' or ‘windspeed'. If they were right they could quickly crack that message, and thereby deduce the Enigma settings for that day. For the rest of the day, other, more valuable, messages could be broken with ease.

When they failed to guess weather words, the British would try
and put themselves in the position of the German Enigma operators to guess other keywords. A sloppy operator might address the receiver by a first name or he might have developed idiosyncrasies which were known to the code-breakers. When all else failed and German traffic was flowing unchecked, it is said that the British Cypher School even resorted to asking the RAF to mine a particular German harbour. Immediately the German harbour-master would send an encrypted message which would be intercepted by the British. The code-breakers could be confident that the message contained words like ‘mine', ‘avoid' and ‘map reference'. Having cracked this message, Turing would have that day's Enigma settings and any further German traffic was vulnerable to rapid decipherment.

On 1 February 1942 the Germans added a fourth wheel to Enigma machines which were employed for sending particularly sensitive information. This was the greatest escalation in the level of encryption during the war, but eventually Turing's team fought back by increasing the efficiency of the bombes. Thanks to the Cypher School, the Allies knew more about their enemy than the Germans could ever have suspected. The impact of German U-boats in the Atlantic was greatly reduced and the British had advanced warning of attacks by the Luftwaffe. The code-breakers also intercepted and deciphered the exact position of German supply ships, allowing British destroyers to be sent out to sink them.

At all times the Allied forces had to take care that their evasive actions and uncanny attacks did not betray their ability to decipher German communications. If the Germans suspected that Enigma had been broken then they would increase their level of encryption, and the British might be back to square one. Hence there were occasions when the Cypher School informed the Allies of an imminent attack, and the Allies chose not to take extreme
countermeasures. There are even rumours that Churchill knew that Coventry was to be targeted for a devastating raid, yet he chose not to take special precautions in case the Germans became suspicious. Stuart Milner-Barry who worked with Turing denies the rumour, and states that the relevant message concerning Coventry was not cracked until it was too late.

The restrained use of decoded information worked perfectly. Even when the British used intercepted communications to inflict heavy losses, the Germans did not suspect that the Enigma code had been broken. They believed that their level of encryption was so high that it would be absolutely impossible to crack their codes. Instead they blamed any exceptional losses on the British secret service infiltrating their own ranks.

Because of the secrecy surrounding the work carried out at Bletchley by Turing and his team, their immense contribution to the war effort could never be publicly acknowledged, even for many years after the war. It used to be said that the First World War was the chemists' war and that the Second World War was the physicists' war. In fact, from the information revealed in recent decades, it is probably true to say that the Second World War was also the mathematicians' war – and in the case of a third world war their contribution would be even more critical.

Throughout his code-breaking career Turing never lost sight of his mathematical goals. The hypothetical machines had been replaced with real ones, but the esoteric questions remained. By the end of the war Turing had helped build Colossus, a fully electronic machine consisting of 1500 valves, which were much faster than the electromechanical relays employed in the bombes. Colossus was a computer in the modern sense of the word, and with the extra speed and sophistication Turing began to think of it as a primitive brain – it had a memory, it could process information,
and states within the computer resembled states of mind. Turing had transformed his imaginary machine into the first real computer.

When the war ended Turing continued to build increasingly complex machines, such as the Automatic Computing Engine (ACE). In 1948 he moved to Manchester University and built the world's first computer to have an electronically stored program. Turing had provided Britain with the most advanced computers in the world, but he would not live long enough to see their most remarkable calculations.

In the years after the war Turing had been under surveillance from British Intelligence, who were aware that he was a practising homosexual. They were concerned that the man who knew more about Britain's security codes than anyone else was vulnerable to blackmail and decided to monitor his every move. Turing had largely come to terms with being constantly shadowed, but in 1952 he was arrested for violation of British homosexuality statutes. This humiliation made life intolerable for Turing. Andrew Hodges, Turing's biographer, describes the events leading up to his death:

Alan Turing's death came as a shock to those who knew him … That he was an unhappy, tense, person; that he was consulting a psychiatrist and suffered a blow that would have felled many people – all this was clear. But the trial was two years in the past, the hormone treatment had ended a year before, and he seemed to have risen above it all.

The inquest, on 10 June 1954, established that it was suicide. He had been found lying neatly in his bed. There was froth round his mouth, and the pathologist who did the post-mortem easily identified the cause of death as cyanide poisoning … In the house was a jar of potassium cyanide, and also a jar of cyanide solution. By the side of his bed was half an apple, out of which several bites had been taken. They did not analyse
the apple, and so it was never properly established that, as seemed perfectly obvious, the apple had been dipped in the cyanide.