The essence of modular arithmetic
.
Introduction :
If you have taken math for CS class or tried to understand some cryptography algorithm you probably have been just told that a≡b mod m means that a-b is devisable by m (so have I) but I couldn’t understand why is that useful or what the heck is going on??
Why do we need modular arithmetic?
Almost all crypto algorithms, both symmetric ciphers and asymmetric ciphers, are based on arithmetic within a finite number of elements. Most number sets we are used to, such as the set of natural numbers or the set of real numbers, are infinite. In the following, we introduce modular arithmetic, which is a simple way of performing arithmetic in a finite set of integers.
Let’s look at an example of a finite set of integers from everyday life:
Example 1.4. Consider the hours on a clock. If you keep adding one hour, you obtain:
1h,2h,3h,…,11h,12h,1h,2h,3h,…,11h,12h,1h,2h,3h,…
Even though we keep adding one hour, we never leave the set.
Let’s look at a general way of dealing with arithmetic in such finite sets.
Example 1.5. We consider the set of the nine numbers:
{0,1,2,3,4,5,6,7,8}
We can do regular arithmetic as long as the results are smaller than 9. For instance:
2×3 = 6
4+4 = 8
But what about 8+4? Now we try the following rule: Perform regular integer arithmetic and divide the result by 9. We then consider only the remainder rather than the original result. Since 8+4 = 12, and 12/9 has a remainder of 3, we write: 8+4 ≡ 3 mod 9
Intuition:
The formal definition of the mod is great but it’s not much help when you’re trying to solve a problem(at least for me), instead, you can use this intuition which is already familiar to you:
The number after the mod is called the ring size, which is the maximum known number in the new setting which is the modular world or ring
Let’s consider the clock example in the 12 settings:
Let’s say it’s 16:00 now, how do you interpret that to normal hours? You subtract 12 hours form 16 and you get 4, then it’s 4 PM
So the next time you see the question: what is 17 mod 7 ask your self: in a world contains numbers from 0 to 6 only what would be 17
Use the hour intuition to calculate it if you want, keep subtracting 7s from the modulus until the result is less than the modulus. And that’s the result.
Also the question of 7+5 mod 2: ask yourself in a world that consists only of numbers less than 2: [0,1] what would be 7+5?
I hope that helps :)
References :
Paar C., Pelzl J. (2010) Introduction to Cryptography and Data Security. In: Understanding Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04101-3_1:
