| Line 48: | Line 48: | ||
---- | ---- | ||
| − | This definition may seem a bit counter-intuitive but we will see where it comes from. | + | This definition may seem a bit counter-intuitive but we will see where it comes from. Note that any integer <math> a </math> can be written in the following way: <center> <math> a = q \dot m + r </math> </center> where <math> 0<=r<m </math> and <math> q,m \in \Z </math>. |
| + | |||
| + | If we subtract <math> r </math> from both sides we arrive at <math> a-r= q \dot m </math> which obviously means that <math> a-r </math> is divisible by m. | ||
==[[2015_Summer_Cryptography_Paar_Introduction to Cryptography_Kathryn Marsh and Divya Agarwal _comments | Questions and comments]]== | ==[[2015_Summer_Cryptography_Paar_Introduction to Cryptography_Kathryn Marsh and Divya Agarwal _comments | Questions and comments]]== | ||
Revision as of 08:17, 9 June 2015
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: Modulus 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.
Questions and comments
If you have any questions, comments, etc. please post them here.
Back to 2015 Summer Cryptography Paar
