8.6. Modular Arithmetic 263
8.5.2 Breaking Turing’s Code (Version 1.0)
Let’s consider what happens when the sender transmits asecondmessage using
Turing’s code and the same key. This gives the Nazis two encrypted messages to
look at:
mc 1 Dm 1 k and mc 2 Dm 2 k
The greatest common divisor of the two encrypted messages,mc 1 andmc 2 , is the
secret keyk. 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 recover the secret key
and readeverymessage!
A mathematician as brilliant as Turing is not likely to have overlooked such a
glaring problem, and we can guess that he had a slightly different system in mind,
one based onmodulararithmetic.
8.6 Modular Arithmetic
On the first page of his masterpiece on number theory,Disquisitiones Arithmeticae,
Gauss introduced 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 thatais congruent tobmoduloniffnj.a b/. This is
written
ab .modn/:
For example:
29 15 .mod7/ because 7 j.29 15/:
It’s not useful to allow a modulusn 1 , and so we will assume from now on
that moduli are greater than 1.
There is a close connection between congruences and remainders:
Lemma 8.6.1(Remainder).
ab .modn/ iff rem.a; n/Drem.b; n/:
Proof. By the Division Theorem 8.1.4, there exist unique pairs of integersq 1 ;r 1
andq 2 ;r 2 such that:
aDq 1 nCr 1
bDq 2 nCr 2 ;
