339 pág.


DisciplinaFundamentos de Algoritmos para Computação125 materiais621 seguidores
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
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
Samuel: Obviously.
Bruce: All right. I know, here we go. We fill the 3-gallon jug exactly to the top,
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
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
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
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