Modular Arithmetic
An important question and one that I kept asking if I should dedicate a post to modular arithmetic is “Why is this important?”, and I came to conclude that while at first modular arithmetic can be very easy/ natural at first, it also gets very abstract the further into cryptography we go.
In cryptography, we almost always do arithmetic in finite sets, and not only in modern cryptosystems we will also need it in our next cipher the Shift Cipher you can read more about it here.
Finite Sets
Finite sets are the basis for this post, and it is essential to know going forward in cryptography. So let’s discuss some examples of what is a finite set and what isn’t, and ill try to not give the pure math definitions.
Think of an example of your friend asking you to pick up 4 loaves of bread at the store, then maybe your Mom asks for 3 loaves of bread, then maybe you see it’s on sale so you decide to buy 8 more. You now have just bought 15 loaves of bread. In a perfect world with no limitations of how much the store has that number could be as high as you want. So that would be an example of an infinite set.
To think about finite sets, and a very common example we will use to give an example of modular arithmetic is a clock. Imagine it is 9 o’clock and your friend tells you to meet them in 20 hours, unlike the bakery example you don’t think you’ll meet them at 29 o’clock, you know that that means 5 o’clock. You just instinctively did 9+20=5, and maybe unknowingly did modular arithmetic in a finite set. In fact to introduce you to the notation of modular arithmetic here is how we would write that:
9 + 20 = 29 ≡ 5 mod 12
Where the ‘≡’ means equivalence and ‘mod’ means modulo. Don’t worry if that doesn’t mean anything to you now, that was just to tie an example you know to the notation we will use from now on.
But first, let’s expand a bit on the example before we define it. Notice that 5 is the remainder of 29/12, so for now just think of the answer (in this case 5) as the remainder that we get after division.
Definition
Let a, r, m ∈ ℤ, and m > 0. We write that a ≡ r mod m if m divides (a – r), ie m | (a – r). We call m the modulus and r the remainder.
Note: ℤ is the symbol for the set of integers, and ∈ is the symbol for “an element of”. So a, r, m is an element of the set of integers. If you are unaware of the ‘|’ called the divides symbol, it is different that ‘/’ as it doesn’t actually “divide” it is only notation to state that a number can divide another. Ie in the definition m can divide (a – r).
Examples
Let a = 13, m = 9, and r = ? (we are trying to find the remainder)
Since 9 fits into 13 once, with a remainder of 4 ie 13 ≡ 4 mod 9.
Now by the definition, (a – r) = 13 – 4 = 9, and 9|9 ✓
Notice though that we don’t really have a formula to compute the remainder yet, so let’s give it one.
Given a, m ∈ ℤ, a = q ⋅ m + r, ie given any number we can define it with a ‘q’ quotient, a integer ‘m’ modulo and ‘r’ remainder. But you may notice that we have a problem in that our formula can have multiple answers, this means we have multiple solutions to our ‘r’ remainder. To show this look at this example below:
Let a = 42, m = 9, and 42 = 4 ⋅ 9 + 6, so r = 6. We can also check that 9 | (42 – 6) = 36.
But also: 42 = 3 ⋅ 9 + 15, this also works because 9 | (42 – 15) = 27.
Also: 42 = 5 ⋅ 9 + (-3), this also works because 9 | (42 – (-3)) = 45.
So the takeaway from this, is that the remainder is not unique. Thus we can make the set of numbers of all these remainders, the set would be
{…, -12, -3, 6, 15, 24, …}
We call this an “Equivalence class“. In fact, there are eight other equivalence classes for the modulus 9:
{…, -27, -18, -9, 0, 9, 18, 27, …}
{…, -26, -17, -8, 1, 10, 19, 28, …}
…
{…, -19, -10, -1, 8, 17, 26, 35, …}
Equivalence classes
Definition
The set {…, -8, -3, 2, 7, 12, 17, …} forms an “Equivalence Class” mod 5. All members of the class behave equivalent modulo 5. Note each element is 5 away from each other.
I feel I should make it known as a pure mathematician this is not a rigorous definition, and is only written so you have a better idea of an equivalence class, and will become more clear with an example below.
Examples
Lets look at all equivalence classes modulo 5:
A: {…, -10, -5, 0, 5, 10, …}
B: {…, -9, -4, 1, 6, 11, …}
C: {…, -8, -3, 2, 7, 12, …}
D: {…, -7, -2, 3, 8, 13, …}
E: {…, -6, -1, 4, 9, 14, …}
Notice that all classes are themselves infinite, but don’t contain all the integers. But combined together they do have all the integers. If you don’t believe me just try to think of an integer that wouldn’t be in any of them.
Let’s consider how this is useful with an example, consider the computation below:
13 ⋅ 16 – 8 = 208 – 8 = 200 ≡ 0 mod 5, this can be easily done with a calculator, but probably not so much in your head.
But notice that each element of the equation above can be found in one of our equivalence classes, ie
13 ∈ D
16 ∈ B
8 ∈ D
Recall that “all classes behave equivalent modulo 5”. Therefore, we can use other members of the class, for example, we can take the “easiest” number from D and B to replace our numbers, ie:
3 ⋅ 1 – 3 = 0 ≡ 0 mod 5, this can be easily done in your head.
Important Application
This will be more important when we get into Asymmetric cryptography because all of the main ones like RSA, Diffie-Hellman, and Elliptic Curves all use modular arithmetic and exponentiation. So you may be able to see when the numbers get way bigger how this could speed things up a lot.
Here is an example/ motivation for this:
38 mod 7 = ?
First way: 38 = 6,561 ≡ 2 mod 7 (This way is naive, and the bigger the numbers the slower)
Second Way: 38 = 34 ⋅ 34 = 81 ⋅ 81, we were able to reduce the complexity a bit but still not ideal. But we can reuse our equivalence class trick to replace the 81 with a simpler number. Instead of writing out each class, we can just reduce 81 modulo 7 so: 81 ≡ 4 mod 7, so 38 = 81 ⋅ 81 = 4 ⋅ 4 = 16 ≡ 2 mod 7.
The Takeaway is that we can simplify out problems to much easier problems, and namely faster problems.
So to solve the problem we had earlier of no unique remainder, we choose the smallest positive number from each equivalence class.
Integer Rings
Now with what we know about modular arithmetic, we can now define a new structure based on modular arithmetic using that set we made based on the smalled positive number we get from each equivalence class before.
Definition
The “integer ring” ℤm consists of:
1) The set of ℤm ={0, 1, 2, …, m – 1}
2) Two operators “+” and ” ⋅ ” s.t. for all a, b, c, d ∈ ℤm ,
i) a + b ≡ c mod m
ii) a ⋅ b ≡ d mod m
Here are more properties of rings that are usually provided with proof, but I won’t do that here:
- We can add and multiply any two numbers and the result is always in the ring. A ring is said to be closed.
- Addition and multiplication are associative, e.g., a + (b + c)=(a + b) + c, and a ·(b · c)=(a · b)· c for all a, b, c ∈ ℤm.
- There is the neutral element 0 with respect to addition, i.e., for every element a ∈ ℤm it holds that (a + 0) ≡ a mod m.
- For any element an in the ring, there is always the negative element −a such that a + (−a) ≡ 0 mod m, i.e., the additive inverse always exists.
- There is the neutral element 1 with respect to multiplication, i.e., for every element a ∈ ℤm it holds that a ⋅ 1 ≡ a mod m.
- The multiplicative inverse exists only for some, but not for all, elements. Let a ∈ ℤ, the inverse a-1 is defined such that:
a · a-1 ≡ 1 mod m
If an inverse exists for a, we can divide by this element since b/a ≡ b · a-1 mod m.
Examples
Let m = 9
1) a = 2, then find a-1 = ? By our last property, we know then:
2 · 2-1 ≡ 1 mod 9 (Note that usually 2-1 = 1/2, but we are working in an integer ring, so 1/2 ∉ ℤ9)
2 · 5 ≡ 1 mod 9
So the multiplicative inverse of 2 is 5.
2) a = 6, then find a-1 = ?
Notice, that no matter what we try from elements in ℤ9 we can’t find a solution.
Therefore, the takeaway from this example is that not all elements in an integer ring have a multiplicative inverse. But there is a way to check if an element does, and that is to find the greatest common denominator.
An element from a ring a ∈ ℤm has a multiplicative inverse a-1 if the gcd(a, m) = 1, otherwise called relatively prime.
