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, x
is encrypted as 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?
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
, two numbers and are said to be congruent modulo , if their difference is an integer multiple of . That is, if there exists an integer such that . We write this as . Put another way, and are congruent modulo if there is an integer (which could be positive, negative, or zero) such that . We call the reduction of modulo or say that reduces to . We will use the notation MOD to indicate the reduction (for example: )
Examples#
because is an integer multiple of ( ) because is an integer multiple of ( ) because is an integer multiple of ( ) because is an integer multiple of ( )