《Mathematics for Computer》Lecture 17 numtheory2

6.042/18.062] Mathematics for Computer Science February 24, 2005 Srini devadas and Eric Lehman Lecture notes Number theory ll Image of Alan Turing removed for copyright reasons s The man pictured above is Alan Turing, the most important figure in the history of mputer science. For decades, his fascinating life story was shrouded by government secrecy, societal taboo, and even his own deceptions At 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 mathemat ics 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 ingenius the programmer. Turings paper is all the more remarkable be cause he wrote it in 1936, a full decade before any 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 obviously a brilliant guy who generated lots of amazing ideas. But this lecture is about one of Turings less-amazing deas. It involved codes. It involved number theory. And it was sort of stupid 1 Turing s Code 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 useful

6.042/18.062J Mathematics for Computer Science February 24, 2005 Srini Devadas and Eric Lehman Lecture Notes Number Theory II Image of Alan Turing removed for copyright reasons. The man pictured above 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. At 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 mathemat￾ics 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 ingenius the programmer. Turing’s paper is all the more remarkable be￾cause he wrote it in 1936, a full decade before any 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 obviously 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. 1 Turing’s Code 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 useful­

Number Theory II ness of number theory. He forsaw 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 digital cash systems. Every time you buy a book from Amazon, check your grades on WebsIs, or use a PayPal account, you are relying on number theoretic algorithms Soon after devising his code, Turing disappeared from public view, and half a centur ould pass before the world learned the full story of where he'd gone and what he did there. Well come back to Turings 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 well consider a couple possibilities 1.1 Turing s Code(version 1.0) The first challenge is to translate a text message into an integer so we can perform math ematical 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""could be translated this way c t o 90320151825 Turings code requires the message to be a prime number, so we may need to pad the result with a few more digits to make a prime. In this case, appending the digits 13 gives the number 2209032015182513, which is prime Now here is how the encryption process works. In the description below, m is the unencoded message(which we want to keep secret), 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 m=m·k Decryption The receiver decrypts m* by computing k-m

2 Number Theory II ness of number theory. He forsaw 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 digital cash systems. Every time you buy a book from Amazon, check your grades on WebSIS, or use a PayPal account, you are relying on number theoretic algorithms. 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 possibilities. 1.1 Turing’s Code (Version 1.0) The first challenge is to translate a text message into an integer so we can perform math￾ematical 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: “v i c t o r y” → 22 09 03 20 15 18 25 Turing’s code requires the message to be a prime number, so we may need to pad the result with a few more digits to make a prime. In this case, appending the digits 13 gives the number 2209032015182513, which is prime. Now here is how the encryption process works. In the description below, m is the unencoded message (which we want to keep secret), 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: m∗ = m k· Decryption The receiver decrypts m∗ by computing: m∗ m k = · = m k k

Number Theory Il For example, suppose that the secret key is the prime number k= 22801763489 and the message m is"victory". Then the encrypted message is: =2209032015182513·22801763489 50369825549820718594667857 There are a couple questions one might naturally ask about Turings code 1. How can the sender and receiver ensure that m and k are prime numbers, as re- uired? The general problem of determining whether a large number is prime or compos ite has been studied for centuries, and reasonably good primality tests were known even in Turing s time. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Sax ena announced a primality test that is guaranteed to work on a number n in about (log n)steps. This definitively placed primality testing in the class of"easy"com- putational problems at last. Amazingly, the description of their breakthrough algo- rithm was only thirteen lines long! 2. Is Turings code secure? The Nazis see only the encrypted message m=m-k, so recovering the original mes- sage m requires factoring m*. Despite immense efforts, no really efficient factoring algorithm has ever been found. It appears to be a fundamentally difficult problem, though a breakthrough someday is not impossible. 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 Turings code 1.2 Breaking Turings Code Let's consider what happens when the sender transmits a second message using Turings code and the same key. This gives the Nazis two encrypted messages to look at: m1=m1·k and m2=m2·k The greatest common divisor of the two encrypted messages, mi and mp, is the secret key k. And, as weve seen, the gcd of two numbers can be computed very efficiently. So after the second message is sent, the Nazis can read recover the secret key and read every It is difficult to believe a mathematician as brilliant as Turing could overlook such glaring problem. One possible explanation is that he had a slightly different system mind, one based on modular arithmetic

Number Theory II 3 For example, suppose that the secret key is the prime number k = 22801763489 and the message m is “victory”. Then the encrypted message is: m∗ = m k· = 2209032015182513 · 22801763489 = 50369825549820718594667857 There are a couple questions one might naturally ask about Turing’s code. 1. How can the sender and receiver ensure that m and k are prime numbers, as re￾quired? The general problem of determining whether a large number is prime or compos￾ite has been studied for centuries, and reasonably good primality tests were known even in Turing’s time. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Sax￾ena announced a primality test that is guaranteed to work on a number n in about (log n)12 steps. This definitively placed primality testing in the class of “easy” com￾putational problems at last. Amazingly, the description of their breakthrough algo￾rithm was only thirteen lines long! 2. Is Turing’s code secure? The Nazis see only the encrypted message m∗ = m·k, so recovering the original mes￾sage m requires factoring m∗. Despite immense efforts, no really efficient factoring algorithm has ever been found. It appears to be a fundamentally difficult problem, though a breakthrough someday is not impossible. 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. 1.2 Breaking Turing’s Code 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: m∗ = m1 · k and m∗ 1 2 = m2 · k The greatest common divisor of the two encrypted messages, m∗ and m∗ 2, is the secret 1 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 read recover the secret key and read every message! It is difficult to believe a mathematician as brilliant as Turing could overlook such a glaring problem. One possible explanation is that he had a slightly different system in mind, one based on modular arithmetic

2 Modular arithmetic On page 1 of his masterpiece on number theory, Disquisitiones Arithmeticae, Gauss intro- duced the notion of"congruence". Now, Gauss is another guy who managed to cough up a half-decent idea every now and then, so let's take a look at this one. Gauss said that a is congruent to b modulo n if n (a-b). This is denoted a= b(mod n). For example 29= 15(mod 7) because 7(29-15) Intuitively, the symbol is sort of like an=sign, and the mod 7 describes the specific sense in which 29 is equal-ish to 15. Thus, even though(mod 7) appears over on the right side, it is in no sense more strongly associated with the 15 than the 29; in fact, it actually defines the meaning of the sign Here's another way to think about congruences: congruence modulo n defines a partition of the integers into n sets so that congruent numbers are all in the same set. For example, suppose that were working modulo 3. Then we can partition the integers into 3 sets as follows 0,3,6,9 1,4,7,10, Now integers in the same set are all congruent modulo 3. For example, 6 and-3 are both in the first set, and theyre congruent because their difference, 6 =9, is a multiple of 3 Similarly, 1l and 5 are both in the last set because 11-5=6 is a multiple of 3. On the other hand, numbers in different sets are not congruent. For example, 9 is in the first set and 11 in the last set, and theyre not congruent because 11-9=2 is not a multiple of 3. The upshot is that when arithmetic is done modulo n there are only n really different kinds of number to worry about. In this sense, modular arithmetic is a simplification of ordinary arithmetic and thus is a good reasoning tool There are many useful facts about congruences, some of which are listed in the lemma below. The overall theme is that congruences work a lot like equations, though ther re are a couple exceptions Lemma 1(Facts About Congruences). The following hold forn>1 1.a≡a(modn) 2.a≡b(modm) implies b≡a(modn) 3.a≡b(modm)andb≡c(modn) implies a≡c(modn) 4.a≡b(modn) implies a+c≡b+c(modn) 5.a≡b(modn) implies ac≡be(modn) 6.a≡b(modn)andc≡d(modn) imply a+c≡b+d(modm)

4 Number Theory II 2 Modular Arithmetic On page 1 of his masterpiece on number theory, Disquisitiones Arithmeticae, Gauss intro￾duced the notion of “congruence”. Now, Gauss is another guy who managed to cough up a half­decent idea every now and then, so let’s take a look at this one. Gauss said that a is congruent to b modulo n if n | (a − b). This is denoted a ≡ b (mod n). For example: 29 ≡ 15 (mod 7) because 7 (29 | − 15). Intuitively, the ≡ symbol is sort of like an = sign, and the mod 7 describes the specific sense in which 29 is equal­ish to 15. Thus, even though (mod 7) appears over on the right side, it is in no sense more strongly associated with the 15 than the 29; in fact, it actually defines the meaning of the ≡ sign. Here’s another way to think about congruences: congruence modulo n defines a partition of the integers into n sets so that congruent numbers are all in the same set. For example, suppose that we’re working modulo 3. Then we can partition the integers into 3 sets as follows: { . . . , −6, −3, 0, 3, 6, 9, . . . } { . . . , −5, −2, 1, 4, 7, 10, . . . . . . , −4, −1, 2, 5, 8, 11, . . . } { } Now integers in the same set are all congruent modulo 3. For example, 6 and ­3 are both in the first set, and they’re congruent because their difference, 6 − (−3) = 9, is a multiple of 3. Similarly, 11 and 5 are both in the last set, because 11 − 5 = 6 is a multiple of 3. On the other hand, numbers in different sets are not congruent. For example, 9 is in the first set and 11 in the last set, and they’re not congruent because 11 − 9 = 2 is not a multiple of 3. The upshot is that when arithmetic is done modulo n there are only n really different kinds of number to worry about. In this sense, modular arithmetic is a simplification of ordinary arithmetic and thus is a good reasoning tool. There are many useful facts about congruences, some of which are listed in the lemma below. The overall theme is that congruences work a lot like equations, though there are a couple exceptions. Lemma 1 (Facts About Congruences). The following hold for n ≥ 1: 1. a ≡ a (mod n) 2. a ≡ b (mod n) implies b ≡ a (mod n) 3. a ≡ b (mod n) and b ≡ c (mod n) implies a ≡ c (mod n) 4. a ≡ b (mod n) implies a + c ≡ b + c (mod n) 5. a ≡ b (mod n) implies ac ≡ bc (mod n) 6. a ≡ b (mod n) and c ≡ d (mod n) imply a + c ≡ b + d (mod n)

Number Theory Il 7.a≡b(modm)andc≡d(modn) imply ac≡bd(modn) Proof. We prove only parts 1 and 7; the other parts are proved similarly (part 1)Every integer divides 0, so n (a-a), which means a= a(mod n) (part 7) The assumption a= b(mod n) implies that ac bc(mod n) by part 5. Similarly, the assumption c= d(mod n) implies bc bd(mod n). Therefore, ac bd(mod n)by art 3 There is a close connection between modular arithmetic and the remainder operation which we looked at last time. To clarify this link, lets reconsider the partition of the integers defined by congruence modulo 3 6.-3.0.3.6.9 5,-2,1,4,7,10 Notice that two numbers are in the same set if and only if they leave the same remainder hen divided by 3. The numbers in the first set all leave a remainder of 0 when divided by 3, the numbers in the second set leave a remainder of 1, and the numbers in the third leave a remainder of 2. Furthermore, notice that each number is in the same set as its own remainder. For example 11 and 1l rem 3=2 are both in the same set. Let' s bundle all this happy goodness into a lemma Lemma 2( Congruences and Remainders). The following assertions hold 1.a≡( a rem n)(modn) 2. a=b(mod n) if and only if (a rem n)=(b rem n Proof.(of part 2) By the division algorithm, there exist unique pairs of integers q1, rI and 92, r2 such that a=gin +rI ( where0≤71<m) b= g2n+ra ( where0≤n2<m) In these terms, (a rem n)=rI and(b rem n)=r2. Subtracting the second equation from the first gives: a-b=(qh-q2)n+(r1-r2) (where -n<r1-r2< n) Now a = b(mod n)if and only if n divides the left side. This is true if and only if n divides the right side, which holds if and only if r1-r2 is a multiple of n. Given the bounds onr r2, this happens precisely when r1=r2, which is equivalent to(a rem n)=(b rem n). D

Number Theory II 5 7. a ≡ b (mod n) and c ≡ d (mod n) imply ac ≡ bd (mod n) Proof. We prove only parts 1 and 7; the other parts are proved similarly. (part 1) Every integer divides 0, so n | (a − a), which means a ≡ a (mod n). (part 7) The assumption a ≡ b (mod n) implies that ac ≡ bc (mod n) by part 5. Similarly, the assumption c ≡ d (mod n) implies bc ≡ bd (mod n). Therefore, ac ≡ bd (mod n) by part 3. There is a close connection between modular arithmetic and the remainder operation, which we looked at last time. To clarify this link, let’s reconsider the partition of the integers defined by congruence modulo 3: { . . . , −6, −3, 0, 3, 6, 9, . . . } { . . . , −5, −2, 1, 4, 7, 10, . . . . . . , −4, −1, 2, 5, 8, 11, . . . } { } Notice that two numbers are in the same set if and only if they leave the same remainder when divided by 3. The numbers in the first set all leave a remainder of 0 when divided by 3, the numbers in the second set leave a remainder of 1, and the numbers in the third leave a remainder of 2. Furthermore, notice that each number is in the same set as its own remainder. For example, 11 and 11 rem 3 = 2 are both in the same set. Let’s bundle all this happy goodness into a lemma. Lemma 2 (Congruences and Remainders). The following assertions hold: 1. a ≡ (a rem n) (mod n) 2. a ≡ b (mod n) if and only if (a rem n) = (b rem n) Proof. (of part 2) By the division algorithm, there exist unique pairs of integers q1, r1 and q2, r2 such that: a = q1n + r1 (where 0 ≤ r1 < n) b = q2n + r2 (where 0 ≤ r2 < n) In these terms, (a rem n) = r1 and (b rem n) = r2. Subtracting the second equation from the first gives: a − b = (q1 − q2)n + (r1 − r2) (where −n < r1 − r2 < n) Now a ≡ b (mod n) if and only if n divides the left side. This is true if and only if n divides the right side, which holds if and only if r1−r2 is a multiple of n. Given the bounds on r1 = r2, this happens precisely when r1 = r2, which is equivalent to (a rem n) = (b rem n)

3 Turings Code (Version 2.0) In 1940 France had fallen before Hitler's army, and Britain alone stood against the Nazis western Europe. British resistance depended on a steady flow of supplies brought across the north Atlantic from the United States by convoys of ships. These convoys were engaged in a cat-and-mouse game with German"U-boat"submarines, which prowled sle a g to sink supply ships and starve Britain into submission. The outcome of this struggle pivoted on a balance of information: could the germans locate convoys better than the allies could locate u-boats or vice versa? Germany lost But a critical reason behind Germanys loss was made public only in 1974: the British had broken Germanys naval code, Enigma. Through much of the war, the Allies were able to route convoys around German submarines by listening into German communica tions. The British government didn, t explain how Enigma was broken until 1996. When the analysis was finally released(by the US), the author was none other than alan tur ing. In 1939 he had joined the secret British codebreaking effort at Bletchley Park. There, he played a central role in cracking the German's Enigma code and thus in preventing Britain from falling into Hitler's hands Governments are always tight-lipped about cryptography, but the half-century of offi cial silence about Turings role in breaking Enigma and saving Britain may be related to ome disturbing events after the war Let's consider an alternative interpretation of Turings code. Perhaps we had the basic idea right(multiply the message by the key), but erred in using conventional arithmetic instead of modular arithemtic. Maybe this is what Turing meant Beforehand The sender and receiver agree on a large prime p, which may be made pub- lic. (This will be the modulus for all our arithemtic. They also agree on a secret key k∈{1,2 1} Encryption The message m can be any integer in the set (0, 1, 2, .., p-1; in particular, the message is no longer required to be a prime. The sender encrypts the message m to produce mby computing 2 *=mk rem Decryp (Uh-oh. The decryption step is a problem. We might hope to decrypt in the same way as be- fore: by dividing the encrypted message m* by the key k. The difficulty is that m* is the remainder when mk is divided by p. So dividing m* by k might not even give us an integer! This decoding difficulty can be overcome with a better understanding of arithmeti modulo a prime

6 Number Theory II 3 Turing’s Code (Version 2.0) In 1940 France had fallen before Hitler’s army, and Britain alone stood against the Nazis in western Europe. British resistance depended on a steady flow of supplies brought across the north Atlantic from the United States by convoys of ships. These convoys were engaged in a cat­and­mouse game with German “U­boat” submarines, which prowled the Atlantic, trying to sink supply ships and starve Britain into submission. The outcome of this struggle pivoted on a balance of information: could the Germans locate convoys better than the Allies could locate U­boats or vice versa? Germany lost. But a critical reason behind Germany’s loss was made public only in 1974: the British had broken Germany’s naval code, Enigma. Through much of the war, the Allies were able to route convoys around German submarines by listening into German communica￾tions. The British government didn’t explain how Enigma was broken until 1996. When the analysis was finally released (by the US), the author was none other than Alan Tur￾ing. In 1939 he had joined the secret British codebreaking effort at Bletchley Park. There, he played a central role in cracking the German’s Enigma code and thus in preventing Britain from falling into Hitler’s hands. Governments are always tight­lipped about cryptography, but the half­century of offi­ cial silence about Turing’s role in breaking Enigma and saving Britain may be related to some disturbing events after the war. Let’s consider an alternative interpretation of Turing’s code. Perhaps we had the basic idea right (multiply the message by the key), but erred in using conventional arithmetic instead of modular arithemtic. Maybe this is what Turing meant: Beforehand The sender and receiver agree on a large prime p, which may be made pub￾lic. (This will be the modulus for all our arithemtic.) They also agree on a secret key k ∈ {1, 2, . . . , p − 1}. Encryption The message m can be any integer in the set {0, 1, 2, . . . , p − 1}; in particular, the message is no longer required to be a prime. The sender encrypts the message m to produce m∗ by computing: m∗ = mk rem p ( ) ∗ Decryption (Uh­oh.) The decryption step is a problem. We might hope to decrypt in the same way as be￾fore: by dividing the encrypted message m∗ by the key k. The difficulty is that m∗ is the remainder when mk is divided by p. So dividing m∗ by k might not even give us an integer! This decoding difficulty can be overcome with a better understanding of arithmetic modulo a prime

Number Theory Il 3.1 Multiplicative Inverses The mutiplicative inverse of a number r is another number .- such that T·x Generally, multiplicative inverses exist over the real numbers. For example, the multi- plicative inverse of 3 is 1/3 since The sole exception is that o does not have an inverse On the other hand, inverses generally do not exist over the integers. For example, 7 can not be multiplied by another integer to give 1 Surprisingly, multiplicative inverses do exist when we re working modulo a prime num ber. For example, if were working modulo 5, then 3 is a multiplicative inverse of 7, since 7·3≡1(mod5) All numbers congruent to 3 modulo 5 are also multiplicative inverses of 7; for example 7.8=1(mod 5)as well. The only exception is that numbers congruent to 0 modulo 5 (that is, the multiples of 5)do not have inverses, much as 0 does not have an inverse over the real numbers. Let' s prove this Lemma 3. If p is prime and k is not a multiple of p, then k has a multiplicative inverse Proof. Since p is prime, it has only two divisors: 1 and p. And since k is not a multiple of p, we must have gcd(p, k)=l. Therefore, there is a linear combination of p and k equal to Rearranging terms gives the definition of congruence. Thus, t is a multiplicative inverse of This implies that p| 1-th by the definition of divisibility, and therefore by □ Multiplicative inverses are the key to decryption in Turing s code. Specifically, we can recover the original message by multiplying the encoded message by the inverse of the m.k=(mk rem p). k(mod p E mkk(mod p m(mod p) This shows that m*k- is congruent to the original message m. Since the m was in the p-l, we can recover it exactly taking a remainder m=m'k rem p So now we can decrypt!

Number Theory II 7 3.1 Multiplicative Inverses The mutiplicative inverse of a number x is another number x−1 such that: x x−1 · = 1 Generally, multiplicative inverses exist over the real numbers. For example, the multi￾plicative inverse of 3 is 1/3 since: 1 3 = 1 · 3 The sole exception is that 0 does not have an inverse. On the other hand, inverses generally do not exist over the integers. For example, 7 can not be multiplied by another integer to give 1. Surprisingly, multiplicative inverses do exist when we’re working modulo a prime num￾ber. For example, if we’re working modulo 5, then 3 is a multiplicative inverse of 7, since: 7 3 · ≡ 1 (mod 5) (All numbers congruent to 3 modulo 5 are also multiplicative inverses of 7; for example, 7 8 · ≡ 1 (mod 5) as well.) The only exception is that numbers congruent to 0 modulo 5 (that is, the multiples of 5) do not have inverses, much as 0 does not have an inverse over the real numbers. Let’s prove this. Lemma 3. If p is prime and k is not a multiple of p, then k has a multiplicative inverse. Proof. Since p is prime, it has only two divisors: 1 and p. And since k is not a multiple of p, we must have gcd(p, k) = 1. Therefore, there is a linear combination of p and k equal to 1: sp + tk = 1 Rearranging terms gives: sp = 1 − tk This implies that p | 1 − tk by the definition of divisibility, and therefore tk ≡ 1 (mod p) by the definition of congruence. Thus, t is a multiplicative inverse of k. Multiplicative inverses are the key to decryption in Turing’s code. Specifically, we can recover the original message by multiplying the encoded message by the inverse of the key: m∗ k−1 ≡ (mk rem p) k−1 · · (mod p) ≡ mkk−1 (mod p) ≡ m (mod p) This shows that m∗k−1 is congruent to the original message m. Since the m was in the range 0, 1, . . . , p − 1, we can recover it exactly taking a remainder: m = m∗ k−1 rem p So now we can decrypt!

3.2 Cancellation Another sense in which real number are nice is that one can cancel multiplicative terms In other words if we know that mik= m2k, then can cancel the k's and conclude that m1=m2, provided k+0. In general, cancellation is not valid in modular arithmetic. For example, this congruence is correct: 2.3≡4.3(mod6) But if we cancel the 3 s we reach a false conclusion: 2≡4(mod6) The fact that multiplicative terms can not be cancelled is the most significant sense in which congruences differ from ordinary equations. However, this difference goes away if were working modulo a prime; then cancellation is valid Lemma 4. Suppose p is a prime and k is not a multiple of p. Then ak≡bk(modp) Implies a≡b(modp) Proof. Multiply both sides of the congruence by k- We can use this lemma to get a bit more insight into how Turing s code works. In particular, the encryption operation in Turing,s code permutes the space of messages. This is stated more precisely in the following corollary. Corollary 5. Suppose p is a prime and k is not a multiple of p. Then the sequence (0·k)remp,(1·k)remp,(2.k)remp, k) rem p is a permutation of the sequence 0,1,2,…,(p-1) This remains true if the first term is deleted from each sequence Proof. The first sequence contains p numbers, which are all in the range 0 to p-1 by the definition of remainder. Furthermore, the numbers in the first sequence are all different by part 2 of Lemma 2, mih rem p= m2k rem p if and only if mI m2(mod p), and no two numbers in the range 0, 1,.,p-1 are congruent modulo p. Thus, the first sequence must contain all of the numbers from 0 to p-1 in some order. The claim remains true if the first terms are deleted because both sequences begin with 0 For example, suppose p=5 and k= 3. Then the sequence 3)rem5,(1·3)rem5,(2.3)rem5,(3·3)rem5,(43)rem5 is a permutation of 0, 1, 2, 3, 4 and the last four terms are a permutation of 1, 2,3,4.As long as the Nazis don, t know the secret key ki, they don't know how the message space is permuted by the process of encryption and thus can t read encoded messages

8 Number Theory II 3.2 Cancellation Another sense in which real number are nice is that one can cancel multiplicative terms. In other words, if we know that m1k = m2k, then can cancel the k’s and conclude that m1 = m2, provided k �= 0. In general, cancellation is not valid in modular arithmetic. For example, this congruence is correct: 2 3 · · ≡ 4 3 (mod 6) But if we cancel the 3’s, we reach a false conclusion: 2 ≡ 4 (mod 6) The fact that multiplicative terms can not be cancelled is the most significant sense in which congruences differ from ordinary equations. However, this difference goes away if we’re working modulo a prime; then cancellation is valid. Lemma 4. Suppose p is a prime and k is not a multiple of p. Then ak ≡ bk (mod p) implies a ≡ b (mod p) Proof. Multiply both sides of the congruence by k−1 . We can use this lemma to get a bit more insight into how Turing’s code works. In particular, the encryption operation in Turing’s code permutes the space of messages. This is stated more precisely in the following corollary. Corollary 5. Suppose p is a prime and k is not a multiple of p. Then the sequence: � � (0 · k) rem p, (1 · k) rem p, (2 · k) rem p, . . . , (p − 1) · k rem p is a permutation of the sequence: 0, 1, 2, . . . , (p − 1) This remains true if the first term is deleted from each sequence. Proof. The first sequence contains p numbers, which are all in the range 0 to p − 1 by the definition of remainder. Furthermore, the numbers in the first sequence are all different; by part 2 of Lemma 2, m1k rem p = m2k rem p if and only if m1 ≡ m2 (mod p), and no two numbers in the range 0, 1, . . . , p ­ 1 are congruent modulo p. Thus, the first sequence must contain all of the numbers from 0 to p − 1 in some order. The claim remains true if the first terms are deleted, because both sequences begin with 0. For example, suppose p = 5 and k = 3. Then the sequence: (0 � · 3) rem 5 �� � , (1 � · 3) rem 5 �� � , (2 � · 3) rem 5 �� � , (3 � · 3) rem 5 �� � , (4 � · 3) rem 5 �� � =0 =3 =1 =4 =2 is a permutation of 0, 1, 2, 3, 4 and the last four terms are a permutation of 1, 2, 3, 4. As long as the Nazis don’t know the secret key k, they don’t know how the message space is permuted by the process of encryption and thus can’t read encoded messages

Number Theory Il 3.3 Fermat's Theorem A remaining challenge in using Turing s code is that decryption requires the inverse of the secret key k. But how can we find an inverse of k? One approach is to rely on Fermats Theorem which is much easier than his famous last theorem - and more useful Theorem 6(Fermat's Theorem). Suppose p is a prime and k is not a multiple of p. Then Imo Proof. We reason as follows 1·2·3…(p-1)≡( k rem p)·(2 e ren p).(3 k rem p)…(P-1) k rem p)(modp) ≡k·2k·3k…(p-1)k(modp) k lod The expressions on the first line are actually equal, by Corollary 5, so they are certainly congruent modulo p. The second step uses part 1 of Lemma 2. In the third step, we rearrange terms in the product Now (p-1)! can not be a multiple of p, because the prime factorizations of 1, 2, ..,(p 1)contain only primes smaller than p. Therefore, we can cancel (p-1)! from the first expression and the last by lemma 4, which proves the claim Here is how we can find inverses using Fermat's Theorem Suppose p is a prime and k is not a multiple of p. Then, by Fermat's Theorem, we know that kP2·k≡1(modp) Therefore, kp- must be a multiplicative inverse of k For example, suppose that we want the multiplicative inverse of 6 modulo 17. Then we need to compute 6 rem 17, which we can do by successive squaring. All the congruences below hold modulo 17 62≡36≡2 64≡(62)2=22=4 615≡68.64.62.6≡16.4.2.6≡3 Therefore, 6 5 rem 17=3. Sure enough, 3 is the multiplicative inverse of 6 modulo 17, 3.6≡1(mod17) e In general, i we were working modulo a prime p, finding a multiplicative inverse by ng every value between 1 and p-l would require about p operations. However, the approach above requires only about log p operations, which is far better when p is large

Number Theory II 9 3.3 Fermat’s Theorem A remaining challenge in using Turing’s code is that decryption requires the inverse of the secret key k. But how can we find an inverse of k? One approach is to rely on Fermat’s Theorem, which is much easier than his famous Last Theorem— and more useful. Theorem 6 (Fermat’s Theorem). Suppose p is a prime and k is not a multiple of p. Then: kp−1 ≡ 1 (mod p) Proof. We reason as follows: 1 2 3 · · · · ·(p − 1) ≡ (k rem p) · (2k rem p) · (3k rem p)· · ·((p − 1)k rem p) (mod p) ≡ k · 2k · 3k · · ·(p − 1)k (mod p) ≡ (p − 1)! kp−1 · (mod p) The expressions on the first line are actually equal, by Corollary 5, so they are certainly congruent modulo p. The second step uses part 1 of Lemma 2. In the third step, we rearrange terms in the product. Now (p−1)! can not be a multiple of p, because the prime factorizations of 1, 2, . . . ,(p− 1) contain only primes smaller than p. Therefore, we can cancel (p − 1)! from the first expression and the last by Lemma 4, which proves the claim. Here is how we can find inverses using Fermat’s Theorem. Suppose p is a prime and k is not a multiple of p. Then, by Fermat’s Theorem, we know that: kp−2 · k ≡ 1 (mod p) Therefore, kp−2 must be a multiplicative inverse of k. For example, suppose that we want the multiplicative inverse of 6 modulo 17. Then we need to compute 615 rem 17, which we can do by successive squaring. All the congruences below hold modulo 17. 62 ≡ 36 ≡ 2 64 ≡ (62 ) 2 ≡ 22 ≡ 4 68 ≡ (64 ) 2 ≡ 42 ≡ 16 615 ≡ 68 64 62 · · · · · 6 ≡ 16 · 4 2 6 ≡ 3 Therefore, 615 rem 17 = 3. Sure enough, 3 is the multiplicative inverse of 6 modulo 17, since: 3 6 · ≡ 1 (mod 17) In general, if we were working modulo a prime p, finding a multiplicative inverse by trying every value between 1 and p − 1 would require about p operations. However, the approach above requires only about log p operations, which is far better when p is large

Number Theory Il 3.4 Breaking Turing s Code- Again German weather reports were not encrypted with the highly-secure Enigma system. After all, so what if the allies learned that there was rain off the south coast of Iceland? But amazingly, this practice provided the British with a critical edge in the Atlantic naval battle during 1941 The problem was that some of those weather reports had originally been transmitted from U-boats out in the Atlantic. Thus, the British obtained both unencrypted reports and the same reports encrypted with Enigma. By comparing the two, the British were able to determine which key the germans were using that day and could read all other Enigma-encoded traffic Today, this would be called a known-plaintext attack Let's see how a known-plaintext attack would work against Turing s code. Suppose that the nazis know both m and m' where m≡mk(modp) Now they can comput mP.m*=mp-(mk rem p)(mod p (def. of m") mP-2·mk(modp) (part 2 of Lemma 2) ≡m-1k(modp) (simplification) ≡k(modp) Now the Nazis have the secret key k and can decrypt any message This is a huge vulnerability, so Turings code has no practical value. Fortunately, Tur ing got better at cryptography after devising this code; his subsequent cracking of Enigma surely saved thousands of lives if not the whole of Britain 4 Postscrip A few years after the war, Turings home was robbed. Detectives soon determined that a former homosexual lover of Turing s had conspired in the robbery. So they arrested him that is, they arrested alan turing. Because at that time, homosexuality was a crime in Britain, punishable by up to two years in prison. Turing was sentenced to a humiliating hormonal"treatment"for his homosexuality: he was given estrogen injections. He began to develop breasts Three years later, Alan Turing the founder of computer science, was dead. His mother explained what happened in a biography of her own son. Despite her repeated warnings, Turing carried out chemistry experiments in his own home. Apparently, her worst fear was realized: by working with potassium cyanide while eating an apple, he poisoned

10 Number Theory II 3.4 Breaking Turing’s Code— Again German weather reports were not encrypted with the highly­secure Enigma system. After all, so what if the Allies learned that there was rain off the south coast of Iceland? But, amazingly, this practice provided the British with a critical edge in the Atlantic naval battle during 1941. The problem was that some of those weather reports had originally been transmitted from U­boats out in the Atlantic. Thus, the British obtained both unencrypted reports and the same reports encrypted with Enigma. By comparing the two, the British were able to determine which key the Germans were using that day and could read all other Enigma­encoded traffic. Today, this would be called a known­plaintext attack. Let’s see how a known­plaintext attack would work against Turing’s code. Suppose that the Nazis know both m and m∗ where: m∗ ≡ mk (mod p) Now they can compute: mp−2 m∗ ≡ mp−2 · (mk rem p) (mod p) (def. of m∗ · ) ≡ mp−2 · mk (mod p) (part 2 of Lemma 2) ≡ mp−1 · k (mod p) (simplification) ≡ k (mod p) (Fermat’s Theorem) Now the Nazis have the secret key k and can decrypt any message! This is a huge vulnerability, so Turing’s code has no practical value. Fortunately, Tur￾ing got better at cryptography after devising this code; his subsequent cracking of Enigma surely saved thousands of lives, if not the whole of Britain. 4 Postscript A few years after the war, Turing’s home was robbed. Detectives soon determined that a former homosexual lover of Turing’s had conspired in the robbery. So they arrested him; that is, they arrested Alan Turing. Because, at that time, homosexuality was a crime in Britain, punishable by up to two years in prison. Turing was sentenced to a humiliating hormonal “treatment” for his homosexuality: he was given estrogen injections. He began to develop breasts. Three years later, Alan Turing, the founder of computer science, was dead. His mother explained what happened in a biography of her own son. Despite her repeated warnings, Turing carried out chemistry experiments in his own home. Apparently, her worst fear was realized: by working with potassium cyanide while eating an apple, he poisoned himself