Modular arithmetic

Modular arithmetic is a type of arithmetic for integers (whole numbers) which “wraps around” when we reach a certain number, called the modulus.

Since the English alphabet has 26 letters, we’re particularly interested at the moment in arithmetic with modulus 26 (“mod 26”); if we have two integers (x) and (y) which, when divided by 26, give the same remainder term, we consider those two integers to be equivalent (mod 26). To represent this, we write

[xequiv y text{ (mod 26).}]

When we divide 27 by 26, the remainder is 1, so we write (27equiv 1) (mod 26). Similarly, (28equiv 2) (mod 26) and (29equiv 3) (mod 26), so modular arithmetic is doing exactly what we wanted here!

The only thing that we need to be careful about here is what we do with the letter (Z): this is the 26th letter of the alphabet, but (26equiv 0) (mod 26), since when we divide 26 by itself we get a remainder of 0. So it might sometimes be more convenient to think of (Z) as the “zeroth letter of the alphabet”! Hopefully you won’t find this too confusing: it might help to think of (Z) as being the letter that comes immediately before (A) when we wrap the alphabet around a circle.

As an aside, it’s worth pointing out that you’re already familiar with modular arithmetic from telling the time. If you’re using a 12-hour clock and it’s currently 10.00, then the time 6 hours later will be 4.00: this is because (16equiv 4) (mod 12). Similarly, if you’re using a 24-hour clock and it’s currently 21.00, then the time 9 hours later will be 06.00, because (30equiv 6) (mod 24).

Terminology

As we progress through the course, we’re going to need to make a clear distinction between the original (unencrypted) message and the output of our encryption algorithm (the encrypted message). We shall refer to the unencrypted message as plaintext – for us this will typically be written in English – and to the encrypted message as ciphertext.

Thus we see that encrypting plaintext using the Caesar cipher is just the same as adding 3 (mod 26); to decrypt the resulting ciphertext we just need to subtract 3 (mod 26). But of course there’s nothing special about adding or subtracting 3: doing the same with any number would give us a valid shift cipher. The only important thing to remember is that, once we have chosen a number by which to shift (let’s call it (d)), we have to add (d) (mod 26) to all numbers when performing the encryption.

For example, if we choose (d=13), then to see how the resulting shift cipher will encrypt the letter (S) (the 19th letter of the alphabet), we calculate (19 +d = 19+13 = 32 equiv 6) (mod 26), and so (Sto F) (the 6th letter of the alphabet). This shift cipher is called ROT13 (“Rotate by 13 places”): adding and subtracting 13 have the same effect when working mod 26, so in this case we can actually recover the plaintext by enciphering the ciphertext. ROT13 is commonly used in online forums to hide spoilers etc: it’s very easy to decipher, but prevents people accidentally reading something that they didn’t want to know!