339 pág.

# MatemathicsForComputerScientists

Pré-visualização50 páginas

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\u2019s see how a known-plaintext attack would work against Turing\u2019s code. Suppose that the Nazis know bothm andm\u2032 where: m\u2032 \u2261 mk (mod p) Number Theory I 59 Now they can compute: mp\u22122 ·m\u2032 \u2261 mp\u22122 ·mk (mod p) \u2261 mp\u22121 · k (mod p) \u2261 k (mod p) The last step relies on Fermat\u2019s Theorem. Now the Nazis have the secret key k and can decrypt any message! This is a huge vulnerability, so Turing\u2019s 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. A few years after the war, Turing\u2019s home was robbed. Detectives soon determined that a former homosexual lover of Turing\u2019s 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 \u201ctreatment\u201d 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. However, Turing remained a puzzle to the very end. His mother was a devoutly re- ligious woman who considered suicide a sin. And, other biographers have pointed out, Turing had previously discussed committing suicide by eating a poisoned apple. Evi- dently, Alan Turing, who founded computer science and saved his country, took his own life in the end, and in just such a way that his mother could believe it was an accident. 60 Number Theory I Chapter 5 Number Theory II 5.1 Die Hard Simon: On the fountain, there should be 2 jugs, do you see them? A 5-gallon and a 3-gallon. Fill one of the jugs with exactly 4 gallons of water and place it on the scale and the timer will stop. You must be precise; one ounce more or less will result in detonation. If you\u2019re still alive in 5 minutes, we\u2019ll speak. Bruce: Wait, wait a second. I don\u2019t get it. Do you get it? Samuel: No. Bruce: Get the jugs. Obviously, we can\u2019t fill the 3-gallon jug with 4 gallons of water. Samuel: Obviously. Bruce: All right. I know, here we go. We fill the 3-gallon jug exactly to the top, right? Samuel: Uh-huh. Bruce: Okay, nowwe pour this 3 gallons into the 5-gallon jug, giving us exactly 3 gallons in the 5-gallon jug, right? Samuel: Right, then what? Bruce: All right. We take the 3-gallon jug and fill it a third of the way... Samuel: No! He said, \u201cBe precise.\u201d Exactly 4 gallons. Bruce: Shit. Every cop within 50 miles is running his ass off and I\u2019m out here playing kids games in the park. Samuel: Hey, you want to focus on the problem at hand? 62 Number Theory II This is from the movieDie Hard 3: With a Vengance. Bruce Willis and Samuel L. Jackson are cops trying to disarm Simon\u2019s diabolical bomb. In the nick of time, they find a solu- tion. On the surface, Die Hard 3 is just a B-grade action movie; however, I think the inner message of the film is that everyone should learn at least a little number theory. 5.1.1 Death by Induction Apparently, Die Hard 4: Die Hardest is planned for release in 2005. In this new film, Bruce just happens to stumble into another terrorist plot while on vacation. But the villian is even more devious this time: Bruce is given a 3-gallon jug and a 6-gallon jug and must measure out exactly 4 gallons. Some scratchwork suggests that the task is impossible. But surely we\u2019d all rest easier if we could mathematically prove that there can be no Die Hard 5. Let\u2019s try an inductive proof that Bruce can not produce exactly 4 gallons of water using 3 and 6-gallon jugs. The first difficulty is that induction always proves that some state- ment holds for all values of a natural variable n, but no such natural variable appears in the problem statement. In general, however, in problems where we want to show that some condition always holds, a good choice is to let n be a number of steps or operations. In this case, we can let n be the number of times water is poured. Then we can try to prove that for all n \u2265 0, neither jug contains exactly 4 gallons of water after n steps. At least we\u2019ve now recast the problem in a form that makes induction applicable. Let\u2019s see how the argument works out. Theorem 32. Bruce dies. Proof. The proof is by induction. Let P (n) be the proposition, \u201cNeither jug contains 4 gallons after n steps.\u201d In the base case, P (0) is true because both jugs are initially empty. Now we assume that P (n) is true in order to prove P (n + 1); that is, we assume that neither jug contains 4 gallons after n steps and prove that neither jug contains 4 gallons after n+ 1 steps. Umm... We\u2019re stuck! The proof can not be completed. The fact that neither jug contains 4 gallons of water after n steps is not sufficient to prove that neither jug can contain 4 gallons after n + 1 steps. For example, after n steps each jug might hold 2 gallons of water. But then combining their contents in the 6-gallon jug would produce 4 gallons. In logical terms, we can\u2019t hope to prove that P (n) implies P (n + 1), because that\u2019s not even true: P (n) does not imply P (n+ 1)! Our first recourse when the inductive step falls apart is to strengthen the induction hypothesis. For example, further scratchwork suggests that the number of gallons in each jug is always a multiple of 3. So we might try again with the induction hypothesis, \u201cAfter n steps, both jugs contains a multiple of 3 gallons.\u201d In fact, this approach goes through. Number Theory II 63 But we\u2019re going to use some number theory to knock off all these water jug problems. For example, what if we want to get 3 gallons using a 17-gallon jug and a 19-gallon jug? Or 1 gallon with 777 and 1001-gallon jugs? 5.1.2 A General Theorem Suppose that we have jugs with capacities a and b. Let\u2019s carry out a few arbitrary opera- tions and see what happens. The state of the system at each step is described below with a pair of numbers (x, y), where x is the amount of water in the jug with capacity a and y is the amount in the jug with capacity b. (0, 0)\u2192 (a, 0) fill first jug \u2192 (a\u2212 b, b) fill second jug from first \u2192 (a\u2212 b, 0) empty second jug \u2192 (a\u2212 2b, b) fill second jug from first \u2192 (a\u2212 2b, 0) empty second jug \u2192 (0, a\u2212 2b) empty first jug into second \u2192 (a, a\u2212 2b) fill first jug \u2192 (2a\u2212 3b, b) fill second jug from first Of course, we\u2019re making some assumptions about the relative capacities of the two jugs here. But another point leaps out: at every step, the amount of water in each jug is of the form s · a+ t · b for some integers s and t. An expression of this form is called a linear combination of a and b. Furthermore, at least one of the jugs is empty or full at all times. This sounds like an assertion that we might be able to prove by induction! Lemma 33. Suppose that we have water jugs with capacities a and b. Then the amount of water in each jug is always a linear