Dilip
<
[email protected]> 12 Dec 2020
========================================================================
Cryptonomicon
This is probably the best fiction I've read in 2020. It's an old book,
published back in 1999. It's also a famous book - almost everyone I
have come across since I started reading it has told me that they've
heard of it.
I had never heard of it till somebody on another more popular internet
protocol recommended this book. I picked it up around the last week of
November 2020 and went over it slowly over 3 weeks. It's a big book -
there's a lot of great content in there.
Like any good book, I think this book has changed something deep in me.
It will probably take a year or two for these changes to emerge and
start being visible. I think it'll have something to do with how I view
my role as an engineer participating in our society.
I wouldn't recommend this book to everyone. However, if you have
stumbled upon this page, you're probably in the target audience for
this book. You'll either hate it or absolutely love it.
Here's a copy-paste of one of my favorite explanations from the book.
Chapter 16. CYCLES
...
"Excuse me." Alan suddenly brakes and jumps off his bicycle. He lifts the
rear wheel from the pavement, gives it a spin with his free hand, then
reaches down and gives the chain a momentary sideways tug. He is watching
the mechanism intently, interrupted by a few aftersneezes.
The chain of Turing’s bicycle has one weak link. The rear wheel has one
bent spoke. When the link and the spoke come into contact with each
other, the chain will part and fall onto the road. This does not happen
at every revolution of the wheel—otherwise the bicycle would be
completely useless. It only happens when the chain and the wheel are in a
certain position with respect to each other.
Based upon reasonable assumptions about the velocity that can be
maintained by Dr. Turing, an energetic bicyclist (let us say 25 km/hr)
and the radius of his bicycle’s rear wheel (a third of a meter), if the
chain’s weak link hit the bent spoke on every revolution, the chain would
fall off every one-third of a second.
In fact, the chain doesn’t fall off unless the bent spoke and the weak
link happen to coincide. Now, suppose that you describe the position of
the rear wheel by the traditional [theta]. Just for the sake of
simplicity, say that when the wheel starts in the position where the bent
spoke is capable of hitting the weak link (albeit only if the weak link
happens to be there to be hit) then [theta] = 0. If you’re using degrees
as your unit, then, during a single revolution of the wheel, [theta] will
climb all the way up to 359 degrees before cycling back around to 0, at
which point the bent spoke will be back in position to knock the chain
off And now suppose that you describe the position of the chain with the
variable C, in the following very simple way: you assign a number to each
link on the chain. The weak link is numbered 0, the next is 1, and so on,
up to l - 1 where l is the total number of links in the chain. And again,
for simplicity’s sake, say that when the chain is in the position where
its weak link is capable of being hit by the bent spoke (albeit only if
the bent spoke happens to be there to hit it) then C = 0.
For purposes of figuring out when the chain is going to fall off of Dr.
Turing’s bicycle, then, everything we need to know about the bicycle is
contained in the values of [theta] and of C. That pair of numbers defines
the bicycle’s state. The bicycle has as many possible states as there can
be different values of ([theta], C) but only one of those states, namely
(0, 0), is the one that will cause the chain to fall off onto the road.
Suppose we start off in that state; i.e., with ([theta] = 0, C = 0), but
that the chain has not fallen off because Dr. Turing (knowing full well
his bicycle’s state at any given time) has paused in the middle of road
(nearly precipitating a collision with his friend and colleague Lawrence
Pritchard Waterhouse, because his gas mask blocks his peripheral vision).
Dr. Turing has tugged sideways on the chain while moving it forward
slightly, preventing it from being hit by the bent spoke. Now he gets on
the bicycle again and begins to pedal forward. The circumference of his
rear wheel is about two meters, and so when he has moved a distance of
two meters down the road, the wheel has performed a complete revolution
and reached the position [theta] = 0 again—that being the position,
remember, when its bent spoke is in position to hit the weak link.
What of the chain? Its position, defined by C, begins at 0 and reaches 1
when its next link moves forward to the fatal position, then 2 and so on.
The chain must move in synch with the teeth on the sprocket at the center
of the rear wheel, and that sprocket has n teeth, and so after a complete
revolution of the rear wheel, when [theta] = 0 again, C = n. After a
second complete revolution of the rear wheel, once again [theta] = 0 but
now C = 2n. The next time it’s C = 3n and so on. But remember that the
chain is not an infinite linear thing, but a loop having only l
positions; at C = l it loops back around to C = 0 and repeats the cycle.
So when calculating the value of C it is necessary to do modular
arithmetic—that is, if the chain has a hundred links (l = 100) and the
total number of links that have moved by is 135, then the value of C is
not 135 but 35. Whenever you get a number greater than or equal to l you
just repeatedly subtract l until you get a number less than l. This
operation is written, by mathematicians, as mod l. So the successive
values of C, each time the rear wheel spins around to [theta] = 0, are
Ci = n mod l, 2n mod l, 3n mod l,. . .,in mod l
where i = (1, 2, 3, . . . [infinity])
more or less, depending on how close to infinitely long Turing wants to
keep riding his bicycle. After a while, it seems infinitely long to
Waterhouse.
Turing’s chain will fall off when his bicycle reaches the state ([theta]
= 0, C = 0) and in light of what is written above, this will happen when
i (which is just a counter telling how many times the rear wheel has
revolved) reaches some hypothetical value such that in mod l = 0, or, to
put it in plain language, it will happen if there is some multiple of n
(such as, oh, 2n, 3n, 395n or 109,948,368,443n) that just happens to be
an exact multiple of l too. Actually there might be several of these
so-called common multiples, but from a practical standpoint the only one
that matters is the first one—the least common multiple, or LCM—because
that’s the one that will be reached first and that will cause the chain
to fall off.
If, say, the sprocket has twenty teeth (n 20) and the chain has a hundred
teeth (l 100) then after one turn of the wheel we’ll have C 20, after two
turns C = 40, then 60, then 80, then 100. But since we are doing the
arithmetic modulo 100, that value has to be changed to zero. So after
five revolutions of the rear wheel, we have reached the state ([theta] =
0, C = 0) and Turing’s chain falls off. Five revolutions of the rear
wheel only gets him ten meters down the road, and so with these values of
l and n the bicycle is very nearly worthless. Of course, this is only
true if Turing is stupid enough to begin pedaling with his bicycle in the
chain-falling-off state. If, at the time he begins pedaling, it is in the
state ([theta] = 0, C = 1) instead, then the successive values will be C
21, 41, 61, 81, 1, 21, . . . and so on forever—the chain will never fall
off. But this is a degenerate case, where "degenerate," to a
mathematician, means "annoyingly boring." In theory, as long as Turing
put his bicycle into the right state before parking it outside a
building, no one would be able to steal it—the chain would fall off after
they had ridden for no more than ten meters.
But if Turing’s chain has a hundred and one links (l = 101) then after
five revolutions we have C = 100, and after six we have C = 19, then
C = 39, 59, 79, 99, 18, 38, 58, 78, 98, 17, 37, 57, 77, 97, 16, 36, 56,
76, 96, 15, 35, 55, 75, 95, 14, 34, 54, 74, 94, 13, 33, 53, 73, 93, 12,
32, 52, 72, 92, 11, 31, 51, 71, 91, 10, 30, 50, 70, 90, 9, 29, 49, 69,
89, 8, 28, 48, 68, 88, 7, 27, 47, 67, 87, 6, 26, 46, 66, 86, 5, 25, 45,
65, 85, 4, 24, 44, 64, 84, 3, 23, 43, 63, 83, 2, 22, 42, 62, 82, 1, 21,
41, 61, 81, 0
So not until the 101st revolution of the rear wheel does the bicycle
return to the state ([theta] = 0, C = 0) where the chain falls off.
During these hundred and one revolutions, Turing’s bicycle has proceeded
for a distance of a fifth of a kilometer down the road, which is not too
bad. So the bicycle is usable. However, unlike in the degenerate case, it
is not possible for this bicycle to be placed in a state where the chain
never falls off at all. This can be proved by going through the above
list of values of C, and noticing that every possible value of C—every
single number from 0 to 100—is on the list. What this means is that no
matter what value C has when Turing begins to pedal, sooner or later it
will work its way round to the fatal C = 0 and the chain will fall off.
So Turing can leave his bicycle anywhere and be confident that, if
stolen, it won’t go more than a fifth of a kilometer before the chain
falls off.
The difference between the degenerate and nondegenerate cases has to do
with the properties of the numbers involved. The combination of (n = 20,
l = 100) has radically different properties from (n = 20, l = 101). The
key difference is that 20 and 101 are "relatively prime" meaning that
they have no factors in common. This means that their least common
multiple, their LCM, is a large number—it is, in fact, equal to l × n =
20 × 101 = 2020. Whereas the LCM of 20 and 100 is only 100. The l = 101
bicycle has a long period —it passes through many different states before
returning back to the beginning—whereas the l = 100 bicycle has a period
of only a few states.
Suppose that Turing’s bicycle were a cipher machine that worked by
alphabetic substitution, which is to say that it would replace each of
the 26 letters of the alphabet with some other letter. An A in the
plaintext might become a T in the ciphertext, B might become F, C might
be come M, and so on all the way through to Z. In and of itself this
would be an absurdly easy cipher to break—kids-in-treehouses stuff. But
suppose that the substitution scheme changed from one letter to the next.
That is, suppose that after the first letter of the plaintext was
enciphered using one particular substitution alphabet, the second letter
of plaintext was enciphered using a completely different substitution
alphabet, and the third letter a different one yet, and so on. This is
called a polyalphabetic cipher.
Suppose that Turing’s bicycle were capable of generating a different
alphabet for each one of its different states. So the state ([theta] = 0,
C = 0) would correspond to, say, this substitution alphabet:
a b c d e f g h i j k l m n o p q r s t u v w x y z
q g u w b i y t f k v n d o h e p x l z r c a s j m
but the state ([theta] = 180, C = 15) would correspond to this
(different) one:
a b c d e f g h i j k l m n o p q r s t u v w x y z
b o r i x v g y p f j m t c q n h a z u k l d s e w
No two letters would be enciphered using the same substitution
alphabet—until, that is, the bicycle worked its way back around to the
initial state ([theta] = 0, C = 0) and began to repeat the cycle. This
means that it is a periodic polyalphabetic system. Now, if this machine
had a short period, it would repeat itself frequently, and would
therefore be useful, as an encryption system, only against kids in
treehouses. The longer its period (the more relative primeness is built
into it) the less frequently it cycles back to the same substitution
alphabet, and the more secure it is.
The three-wheel Enigma is just that type of system (i.e., periodic
polyalphabetic). Its wheels, like the drive train of Turing’s bicycle,
embody cycles within cycles. Its period is 17,576, which means that the
substitution alphabet that enciphers the first letter of a message will
not be used again until the 17,577th letter is reached. But with Shark
the Germans have added a fourth wheel, bumping the period up to 456,976.
The wheels are set in a different, randomly chosen starting position at
the beginning of each message. Since the Germans’ messages are never as
long as 450,000 characters, the Enigma never reuses the same substitution
alphabet in the course of a given message, which is why the Germans think
it’s so good.
- Neal Stephenson, Cryptonomicon
