Contents
The Paar Lectures on Introductory Cryptography
Slectures by Divya Agarwal and Katie Marsh
Link to video on youtube
Accompanying Lecture Notes
1. Why is Modular Arithmetic Important for Crpytography We are used to dealing with problems in math classes that deal with infinite sets of numbers, such as the real numbers and integers. Cryptosystems however are often based on finite and discrete sets and modular arithmetic is at the heart of many cryptosystems. We need to know about modular arithmetic in order to compute within these systems. However, everyone has some experience with modular arithmetic whether they are aware of it or not. Telling time, though time possibly is infinite, is a finite system. If we are talking about the time, we don't have an infinite number of hours to work with, we only have 12 (or 24 in military time). So this is a finite system and we need modular arithmetic to deal with it. Let's look at an easy example.
Example 1.1: Say it's 10 am and your friend wants to meet up with you after lunch. They tell you to meet them in 5 hours. What time are you going to meet them?
Obviously, you will meet your friend at 3 pm. But $ \ 10+5=15 $. How we write this is $ 15 \equiv 3 \bmod 12 $.
Link to video on youtube
Accompanying Lecture Notes
2. Modular Operator
How do we arrive at 15 on the clock is actually 3? What you need to do is take the remainder of 15 divided by 12 which is 3. We've just seen one example of the modular operator but lets look at the exact definition.
Definition: Modulo Operation
Let a,r,m $ \in \Z $ and m>0. We write
$ a \equiv r \bmod m $
if $ m $ divides $ a-r $.
$ m $ is called the modulus and $ r $ is called the remainder.
This definition may seem a bit counter-intuitive but we will see where it comes from. Note that any integer $ a $ can be written in the following way:
If we subtract $ r $ from both sides we arrive at $ a-r= q*m $ which obviously means that $ a-r $ is divisible by m.
The most common example for modular arithmetic is time as we have seen earlier. Hours are modulo 12 or 24, minutes are modulo 60, months are modulo 12. Lets look at some examples with different modulus.
Example 1.2
- $ a = 13, m=5 $
$ 13 \equiv 3 \bmod 5 $
- $ a = 24, m=12 $
$ 24 \equiv 0 \bmod 12 $
- $ a = -2, m=20 $
$ -2 \equiv 18 \bmod 20 $ because $ -2 = 20*(-1)+18 $
Link to video on youtube
Accompanying Lecture Notes
Notice that if we remove the restriction that $ 0 \leq r<m $ then there are infinite choices for r. For example, $ 42 \equiv 6 \bmod 9 $ because $ 42 = 4*9+6 $ but also $ 42 \equiv 15 \bmod 9 $ because $ 42 = 3*9+15 $.
Therefore the remainder is NOT unique and we get equivalence classes.
3. Equivalence Classes
An equivalence class is the set of numbers that are all equivalent under modulo operation. In the above example $ 42 \equiv 6 \equiv 15 \pmod 9 $ so 42, 6, and 15 are in the same equivalence class for the modulus 9.
Let's look at all the equivalence classes for the modulus 4. This means we are living in a universe which is this set {0,1,2,3}.
The equivalence class of [0] modulo 4 is the set of things which give remainder 0 when divided by 4. So this is all the multiples of 4.
[0] = {...,-12,-8,-4,0,4,8,12,...}
The equivalence class of [1] modulo 4 is the set of things which give remainder 1 when divided by 4. So this is everything that is one higher than a multiple of 4.
[1] = {...,-11,-7,-3,1,5,9,13,...}
We continue in this way.
[2] = {...-6,-2,2,6,10,14,...}
[3] = {...,-9,-5,-1,3,7,11,...}
And these are all the equivalence classes of modulus 4. Equivalence classes are a way of collapsing all in integers in a finite subset, namely {0,1,2,3} in this case.
KEY IDEA All elements in the same equivalence class behave equivalently.
In computation, we can choose any element of an equivalence class we would like. This is incredibly convenient as we can always rewrite number in a way which would make the calculations easier.
References
- C. Paar. Understanding Cryptography. Lecture Notes. Dept. of Electr. Eng. and Information Sciences, Ruhr University.
- C. Paar and J. Pelzl. Understanding Cryptography. A textbook for Student and Practitioners. Springer 2010.
Questions and comments
If you have any questions, comments, etc. please post them here.
Back to 2015 Summer Cryptography Paar
