8.5: Alan Turing

The man pictured in Figure 8.1 is Alan Turing, the most important figure in the history of computer science. For decades, his fascinating life story was shrouded by government secrecy, societal taboo, and even his own deceptions.

Figure 8.1 Alan Turing

At age 24, Turing wrote a paper entitled On Computable Numbers, with an Application to the Entscheidungsproblem. The crux of the paper was an elegant way to model a computer in mathematical terms. This was a breakthrough, because it allowed the tools of mathematics to be brought to bear on questions of computation. For example, with his model in hand, Turing immediately proved that there exist problems that no computer can solve—no matter how ingenious the programmer. Turing’s paper is all the more remarkable because he wrote it in 1936, a full decade before any electronic computer actually existed.

The word “Entscheidungsproblem” in the title refers to one of the 28 mathematical problems posed by David Hilbert in 1900 as challenges to mathematicians of the 20th century. Turing knocked that one off in the same paper. And perhaps you’ve heard of the “Church-Turing thesis”? Same paper. So Turing was a brilliant guy who generated lots of amazing ideas. But this lecture is about one of Turing’s less-amazing ideas. It involved codes. It involved number theory. And it was sort of stupid.

Let’s look back to the fall of 1937. Nazi Germany was rearming under Adolf Hitler, world-shattering war looked imminent, and—like us —Alan Turing was pondering the usefulness of number theory. He foresaw that preserving military secrets would be vital in the coming conflict and proposed a way to encrypt communications using number theory. This is an idea that has ricocheted up to our own time. Today, number theory is the basis for numerous public-key cryptosystems, digital signature schemes, cryptographic hash functions, and electronic payment systems. Furthermore, military funding agencies are among the biggest investors in cryptographic research. Sorry, Hardy!

Soon after devising his code, Turing disappeared from public view, and half a century would pass before the world learned the full story of where he’d gone and what he did there. We’ll come back to Turing’s life in a little while; for now, let’s investigate the code Turing left behind. The details are uncertain, since he never formally published the idea, so we’ll consider a couple of possibilities.

Turing’s Code (Version 1.0)

The first challenge is to translate a text message into an integer so we can perform mathematical operations on it. This step is not intended to make a message harder to read, so the details are not too important. Here is one approach: replace each letter of the message with two digits \((A = 01, B = 02, C = 03\), etc.) and string all the digits together to form one huge number. For example, the message “victory” could be translated this way:

\[\nonumber \begin{array}{cccccccc}
& \mathbf{v} & \mathrm{i} & \mathrm{c} & \mathrm{t} & \mathrm{o} & \mathrm{r} & \mathrm{y} \\
\rightarrow & 22 & 09 & 03 & 20 & 15 & 18 & 25
\end{array}\]

Turing’s code requires the message to be a prime number, so we may need to pad the result with some more digits to make a prime. The Prime Number Theorem indicates that padding with relatively few digits will work. In this case, appending the digits 13 gives the number 2209032015182513, which is prime.

Here is how the encryption process works. In the description below, \(m\) is the unencoded message (which we want to keep secret), \(\hat{m}\) is the encrypted message (which the Nazis may intercept), and \(k\) is the key.

Beforehand The sender and receiver agree on a secret key, which is a large prime \(k\).

Encryption The sender encrypts the message \(m\) by computing:

\[\nonumber \hat{m} = m \cdot k\]

Decryption The receiver decrypts mb by computing:

\[\nonumber \frac{\hat{m}}{k} = m.\]

For example, suppose that the secret key is the prime number \(k = 22801763489\) and the message \(m\) is “victory.” Then the encrypted message is:

\[\begin{aligned} \hat{m} &= m \cdot k \\ &= 2209032015182513 \cdot 22801763489 \\ &= 50369825549820718594667857 \end{aligned}\]

There are a couple of basic questions to ask about Turing’s code.

1. How can the sender and receiver ensure that \(m\) and \(k\) are prime numbers, as required?

The general problem of determining whether a large number is prime or composite has been studied for centuries, and tests for primes that worked well in practice were known even in Turing’s time. In the past few decades, very fast primality tests have been found as described in the text box below.

2. Is Turing’s code secure?

The Nazis see only the encrypted message \(\hat{m} = m \cdot k\), so recovering the original message \(m\) requires factoring \(\hat{m}\). Despite ef b immense efforts, no really ficient factoring algorithm has ever been found. It appears to be a fundamentally difficult problem. So, although a breakthrough someday can’t be ruled out, the conjecture that there is no efficient way to factor is widely accepted. In effect, Turing’s code puts to practical use his discovery that there are limits to the power of computation. Thus, provided \(m\) and \(k\) are sufficiently large, the Nazis seem to be out of luck!

This all sounds promising, but there is a major flaw in Turing’s code.

Primality Testing

It’s easy to see that an integer \(n\) is prime iff it is not divisible by any number from 2 to \([\sqrt{n}]\) (see Problem 1.9). Of course this naive way to test if \(n\) is prime takes more than \([\sqrt{n}]\) steps, which is exponential in the size of \(n\) measured by the number of digits in the decimal or binary representation of \(n\). Through the early 1970’s, no prime testing procedure was known that would never blow up like this.

In 1974, Volker Strassen invented a simple, fast probabilistic primality test. Strassens’s test gives the right answer when applied to any prime number, but has some probability of giving a wrong answer on a nonprime number. However, the probability of a wrong answer on any given number is so tiny that relying on the answer is the best bet you’ll ever make.

Still, the theoretical possibility of a wrong answer was intellectually bothersome—even if the probability of being wrong was a lot less than the probability of an undetectable computer hardware error leading to a wrong answer. Finally in 2002, in a breakthrough paper beginning with a quote from Gauss emphasizing the importance and antiquity of primality testing, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena presented an amazing, thirteen line description of a polynomial time primality test.

This definitively places primality testing way below the exponential effort apparently needed for SAT and similar problems. The polynomial bound on the Agrawal et al. test had degree 12, and subsequent research has reduced the degree to 5, but this is still too large to be practical, and probabilistic primality tests remain the method used in practice today. It’s plausible that the degree bound can be reduced a bit more, but matching the speed of the known probabilistic tests remains a daunting challenge.

Breaking Turing’s Code (Version 1.0)

Let’s consider what happens when the sender transmits a second message using Turing’s code and the same key. This gives the Nazis two encrypted messages to look at:

\[\nonumber \hat{m_1} = m_1 \cdot k\) and \(\hat{m_2} = m_2 \cdot k\]

The greatest common divisor of the two encrypted messages, \(\hat{m_1}\) and \(\hat{m_2}\), is the secret key \(k\). And, as we’ve seen, the GCD of two numbers can be computed very efficiently. So after the second message is sent, the Nazis can recover the secret key and read every message!

A mathematician as brilliant as Turing is not likely to have overlooked such a glaring problem, and we can guess that he had a slightly different system in mind, one based on modular arithmetic.