Modular Arithmetic
A slecture by Kathryn Marsh and Divya Agarwal
based on the Cryptography lecture material of Prof. Paar.
Link to video on youtube
Accompanying Lecture Notes
- 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 $.
- 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 \dot 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 $
$ a \equiv 3 \bmod 5 $
Questions and comments
If you have any questions, comments, etc. please post them here.
Back to 2015 Summer Cryptography Paar
