Chapter 8 Number Theory204
Governments are always tight-lipped about cryptography, but the half-century of
official silence about Turing’s role in breaking Enigma and saving Britain may be
related to some disturbing events after the war. More on that later. Let’s get back to
number theory and consider an alternative interpretation of Turing’s code. Perhaps
we had the basic idea right (multiply the message by the key), but erred in using
conventionalarithmetic instead ofmodulararithmetic. Maybe this is what Turing
meant:
Beforehand The sender and receiver agree on a large primep, which may be made
public. (This will be the modulus for all our arithmetic.) They also agree on
a secret keyk 2 Œ1;p/.
EncryptionThe messagemcan be any integer inŒ0;p/; in particular, the message
is no longer required to be a prime. The sender encrypts the messagemto
producemby computing:
mDrem.mk;p/ (8.7)
Decryption (Uh-oh.)
The decryption step is a problem. We might hope to decrypt in the same way as
before: by dividing the encrypted messagemby the keyk. The difficulty is that
mis theremainderwhenmkis divided byp. So dividingmbykmight not even
give us an integer!
This decoding difficulty can be overcome with a better understanding of arith-
metic modulo a prime.
8.6 Arithmetic with a Prime Modulus
8.6.1 Multiplicative Inverses
Themultiplicative inverseof a numberxis another numberx ^1 such that:
xx ^1 D 1
Generally, multiplicative inverses exist over the real numbers. For example, the
multiplicative inverse of 3 is1=3since:
3
1
3
D 1
