4.3. Modular Arithmetic#

As we noticed in our work with the Caesar Cipher, for each key value there is at least one letter that results in a computed position value that doesn’t fall between 0 and 25. We solved the problem by wrapping the alphabet around back to the letter A. This wrapping around concept is the same way we add when we’re talking about time on a clock. If it were 9:00am and someone asked what the time would be in 6 hours, you would answer 3 o’clock, not 15 o’clock. 3 hours before 1 o’clock would be 10 o’clock, not -2 o’clock. Likewise, if someone asked what ciphertext letter would be obtained by enciphering the plaintext letter x with a key of 5, you would respond C by moving 5 letters to the right down the alphabet, wrapping around once you get to Z.

You’ve probably already realised the couting places along the alphabet is time-consuming and annoying. Much like with telling time, there’s a way to compute values that doesn’t involve counting. In the case of the clock, 9+6=15, which is 3 more than 12 (the number of positions on a clock). We write this fact as 153(mod12) which is read as “15 is equivalent (or congruent) to 3 modulo 12”. Similarly, the letter x is encrypted as 23+5=28, which is 2 more than 26 (the total number of letters in our alphabet). As such, we can write 282(mod26). Now we get the same answer numerically as we would get from counting, 2, which corresponds to the letter C. For large values, we may need to wrap around more than once. For example, what time is it 25 hours after 5 o’clock? 5+25=30, which is 6 hours past two complete turns around the clock. It would be 6 o’clock, also denoted as 306(mod12)

These types of operations will be extremely important in your work in this course. We call this method of addition modulo arithmetic. On a clock the modulus is 12, while in the Casear Cipher the modulus is 26. Let’s define this operation and set some terminology.

Modulo Arithmetic: For a positive integer n, two numbers a and b are said to be congruent modulo n, if their difference ab is an integer multiple of n. That is, if there exists an integer k such that ab=kn. We write this as ab(modn). Put another way, a and b are congruent modulo n if there is an integer k (which could be positive, negative, or zero) such that a=b+kn. We call b the reduction of a modulo n or say that a reduces to b. We will use the notation MOD to indicate the reduction (for example: 28 MOD 26=2)

Examples#

  • 58(mod3) because 58 is an integer multiple of 3 (3=31)

  • 175(mod3) because 175 is an integer multiple of 3 (12=34)

  • 99(mod11) because 99 is an integer multiple of 11 (0=110)

  • 250(mod26) because 250 is an integer multiple of 26 (52=262)