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 \(15 \equiv 3 \pmod{12}\) 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 \(28 \equiv 2 \pmod{26}\). 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 \(30 \equiv 6 \pmod{12}\)
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 \(a − b\) is an integer multiple of \(n\). That is, if there exists an integer \(k\) such that \(a − b = kn\). We write this as \(a \equiv b \pmod{n}\). 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 \text{ MOD } 26 = 2\))
Examples#
\(5 \equiv 8 \pmod{3}\) because \(5 - 8\) is an integer multiple of \(3\) (\(-3 = 3 \cdot -1\))
\(17 \equiv 5 \pmod{3}\) because \(17 - 5\) is an integer multiple of \(3\) (\(12 = 3 \cdot 4\))
\(9 \equiv 9 \pmod{11}\) because \(9 - 9\) is an integer multiple of \(11\) (\(0 = 11 \cdot 0\))
\(-2 \equiv 50 \pmod{26}\) because \(-2 - 50\) is an integer multiple of \(26\) (\(-52 = 26 \cdot -2\))