Suppose you look at a clock and want to know, “what time will it be in five hours?” If it is currently 10 o’clock, you don’t say “15 o’clock,” you say “3 o’clock.” You might say “AM” or “PM,” but that is extra information, not shown on a standard clockface. In the same way, 44 h from now it will be 6 o’clock;  what day, and whether it will be morning or evening, is not given by clockface arithmetic.

What you do when interpreting a clock is to subtract multiples of 12 when necessary. In fact, all you are concerned with is the remainder after division by 12. For example, 10+44 = 54 = 4×12+6; we ignore the 12s and say “6 o’clock.”

Another way of expressing clockface arithmetic is to say calculations are carried out modulo 12, and we might write

                           44+10 = 6(mod 12).

In order to distinguish between modular arithmetic and ordinary arithmetic, it is usual to write this as 44+10 ≡ 6(mod 12), although most people still say “equals.”

The number 12 is called the base or the modulus. We usually express the answer to a modulo 12 problem as one of the numbers in the standard range 0,1,2,...,11,  although we could equally well write 12 instead of 0. (In the particular case of telling the time, we say “12 o’clock,” not “0 o’clock.”)

Another method of telling time is the military, or 24-h clock. This indicates the difference between morning and evening, and is in fact a modulo 24 arithmetic. (In the military clock we say “00:30 h,” not “24:30 h.”)

In the preceding chapter we used binary arithmetic, the arithmetic of even andodd. It is about remainders modulo 2. In that case the addition table is

inary arithmetic comes up in many electrical applications. As an example, think about turning a light on or off. On many lamps, there is a knob that you twist clockwise. If the light is on, twisting the knob changes it to “off.” Similarly twisting from “off” gives “on.” If 1 means “on” and 0 means “off,” and if the process of turning the knob is interpreted as “add 1” (which makes sense if you think of the lamp being off originally), you have

                                                      0+1 = 1, 1+1 = 0,

which is precisely arithmetic modulo 2. The Venn diagram encoding method could be expressed as follows: “the entries E, F, and G are chosen so that the sum of entries in each circle is 0 (modulo 2).”

Additive ciphers use arithmetic modulo 26 (provided the language uses the English alphabet). The Caesar cipher could be expressed as “add 3 modulo 26,” and decoding is “subtract 3 modulo 26,” where the letters are interpreted as numbers  (A = 1, B = 2, and so on up to Z = 26).

This sort of modular arithmetic can be carried out with any integer as modulus.

We can do addition, multiplication, raising to powers, or any arithmetical operation.

For example, in arithmetic modulo 5, the calculation “3³ + 2” is carried out as follows. 3³ = 27 and 27 + 2 = 29. Now 29 ≡ 4(mod 5) (this process of getting rid of 5s and coming down to a number in the standard range is called reducing modulo the base). So the answer is 4. Notice that you can reduce at any stage: the above calculation could have gone 3³ = 27 ≡ 2(mod 5),2+2 = 4.

Sample Problem 1.1 Solve the equation x² ≡ 1(mod 5).

Solution. The easiest technique in this case is to test all the possibilities in the standard range: there are only five of them. We find 0² = 0, 1² = 1, 2² = 4,  3² = 9 ≡ 4, and 4² = 16 ≡ 1. So the answer is “x = 1 or 4.”

One well-known application of modular arithmetic is deciding whether a number is divisible by 9. When we write numbers in the usual way, we observe that 10 ≡ 1(mod 9), 100 ≡ 1(mod 9), 1000 ≡ 1(mod 9), and so on. Moreover, 200 ≡ 2(mod 9), 300 ≡ 3(mod 9), and so on. We can use this to calculate the remainder on division by 9: for example,  3,182 = 3,000+100+80+2≡ 3+1+8+2≡ 14 ≡ 1+4 = 5(mod 9).

مواضيع ذات صلة

The RSA Scheme

Substitution Ciphers

The Vigenère Method

The Caesar Cipher

Physical Secrecy

Secret Writing

Cryptology