Cryptonomicon

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 (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 notpossible 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 Chas 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, I = 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 x n = 20 x 101 = 2020. Whereas the LCM of 20 and 100 is only 100. The 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 changedfrom 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.