Main content
Computer science
Course: Computer science > Unit 2
Lesson 5: Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
Modular multiplication
Let's explore the multiplication property of modular arithmetic:
(A * B) mod C = (A mod C * B mod C) mod C
Example for Multiplication:
Let A=4, B=7, C=6
Let's verify: (A * B) mod C = (A mod C * B mod C) mod C
LHS= Left Hand Side of the Equation
RHS= Right Hand Side of the Equation
LHS = (A * B) mod C
LHS = (4 * 7) mod 6
LHS = 28 mod 6
LHS = 4
RHS = (A mod C * B mod C) mod C
RHS = (4 mod 6 * 7 mod 6) mod 6
RHS = (4 * 1) mod 6
RHS = 4 mod 6
RHS = 4
LHS = RHS = 4
Proof for Modular Multiplication
We will prove that (A * B) mod C = (A mod C * B mod C) mod C
We must show that LHS = RHS
From the quotient remainder theorem we can write A and B as:
A = C * Q1 + R1 where 0 ≤ R1 < C and Q1 is some integer. A mod C = R1
B = C * Q2 + R2 where 0 ≤ R2 < C and Q2 is some integer. B mod C = R2
LHS = (A * B) mod C
LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C
We can eliminate the multiples of C when we take the mod C
LHS = (R1 * R2) mod C
Next let's do the RHS
RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C
Therefore RHS = LHS
LHS = RHS = (R1 * R2 ) mod C
Want to join the conversation?
- I'm a little confused as to why you would choose to do (A mod C * B mod C) mod C, over (A*B) mod C. (And likewise for addition or subtraction) The A*B route seems much simpler...?(13 votes)
- When the numbers are small, under a few billion it's not a big deal to multiply first. But for the really big (100+ digits) numbers used in cryptography, being able to do the mods first, then multiple the residues saves a pile of work.(83 votes)
- Is there an intuitive explanation for modular multiplication (something involving clocks) like there is for modular addition?(12 votes)
- Here's an analogy that might work for you.
Suppose we have:
- a cylinder, which we can just barely wrap a rope of length C around
- a rope, that we have marked every A units
Suppose our rope has B markings from its start. (The rope has length A * B)
We nail the rope to our cylinder and we wrap it clockwise around our cylinder.
(A * B) mod C tells us: how much rope to we need to go clockwise from the nail to reach the end of the rope (we don't care about the length of rope that completely wraps around the cylinder)
It is equivalent to the expression:
(A mod C * B mod C) mod C
A mod C tells us:
How much further (clockwise) a segment of length A will be from the previous segment after wrapping it around the cylinder.
We use B mod C, because if we wrap C segments of length A around the cylinder, the length (A * C) will be evenly divisible by C and we would be just back at the nail i.e. B mod C is the number of segments that actually contribute to the end of the rope being further away from the nail
I would also suggest looking at the "Intuition Behind Modular Addition" section in the modular addition article. Multiplication is essentially just repeated addition.
Hope this makes sense(10 votes)
- Suppose a question is given: X = 12 * 53 mod 32
Now, does it mean X = (12 * 53) mod 32 or X = 12 * (53 mod 32) ?(5 votes)- Unfortunately, it can be used to be mean either.
Hopefully, the context that it is being used in should make it obvious which is meant. If the context does not make it obvious what is meant then the writer should use adequate brackets to make it obvious.
That, being said, most often it will be used to mean: X = (12 * 53) mod 32, but the other usage is not unheard of.(11 votes)
- Just thinking out loud and seeing possibilities: Is there a practical use for cascading Modulus?
(((29 mod 17) mod 7) mod 3) = x
where
29 mod 17 = 12
12 mod 7 = 5
5 mod 3 = 2
x = 2(2 votes)- You could use it to give yourself some more time before people catch on to your RSA, but not much else. And with RSA, you already have a few hundred years anyway. You could also use it to make programmers go hysteric by seeing 500 nested parentheses.(3 votes)
- "LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C
We can eliminate the multiples of C when we take the mod C
LHS = (R1 * R2) mod C"
Could someone please help explain how the top line and the bottom line are identical?
"LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C" is supposed to give us R1 * R2, not (R1 * R2) mod C. There is something I'm missing here.
I can understand how we end up with
"RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C"
Thanks a lot.(2 votes) - In the proof of the RHS how did you get from RHS = (A mod C * B mod C) mod C which is
(R1 mod C * R2 mod C) mod C
to the next step
(R1 * R2 ) mod C
Isn't that what you need to prove?(1 vote)- Explaining the proof
RHS = (A mod C * B mod C) mod C
A mod C = R1
B mod C = R2
substitute these values into the above to get:
RHS = (R1 * R2) mod C
Why (R1 * R2) mod C = (R1 mod C * R2 mod C) mod C isn't enough
We could say the following:
RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2) mod C (since A mod C=R1 and B mod C=R2)
RHS= (R1 mod C* R2 mod C) mod C
(since for any integer X< C, X mod C = X, which is the case for R1 and R2)
This would give us: (R1 * R2) mod C = (R1 mod C* R2 mod C) mod C
(by equating the last two expressions above)
Is showing that:
(R1 * R2) mod C = (R1 mod C* R2 mod C) mod C
the same as showing that:
(A * B) mod C = (A mod C * B mod C) mod C ?
No.
Here's why:
A, B, C are arbitrarily chosen integers.
On the other hand R1,R2 must both be less than C.
If A or B >=C the statements are not equivalent.
Hope this makes sense(4 votes)
- Can someone show me the algebraic hocus pocus that gets us from the first line to the second line?
LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C(2 votes)- No magic involved. It's just multiplying the stuff out in brackets.
Every term in the first set of brackets gets multiplied by every term in the second set of brackets.
(Some schools teach a FOIL method for multiplying binomials)
In general:
(a+b) * (c+d) = ac + ad + bc + bd
So, in the the first line we have:
a = C * Q1
b = R1
c = C * Q2
d = R2
which gives us:
(a+b) * (c+d) = ((C * Q1) + (R1) ) * ((C * Q2) + (R2))
(a+b) * (c+d) = (C * Q1) * (C * Q2) + (C * Q1) * (R2) + (R1) * (C * Q2) + (R1) * (R2)
removing brackets and rearranging terms (to make it more obvious which are multiples of C) we get:
(a+b) * (c+d) = C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R2
Hope this makes sense(2 votes)
- What about Modulo Division?(3 votes)
- This is actually a great question, and I'm surprised it hasn't been commented on (that I can see). First, I want to say something about subtraction so that we have a decent analogy to use.
Subtraction is the inverse operation for addition. One cool thing about the number system is that we can use additive inverses in place of subtraction. In ordinary arithmetic, we would say 4 - 7 = 4 + -7 which has a value -3. However, in modular arithmetic, we don't see those negative values. Instead the additive inverse of a number is that modulus such that when you add it to the number you get 0. (That's really the same idea: -4 is the inverse of 4 because -4 + 4 = 0.) For example, because 2+3=0 mod 5, 3 is the additive inverse of 2 (and vice versa). This means that (x-2) mod 5 and (x+3) mod 5 are going to always be the same.
Now, about division. The analog for an additive inverse is the multiplicative inverse. In ordinary arithmetic, you learned about that as being the reciprocal. We don't have fractions in this arithmetic. If you look at a multiplication table for modular arithmetic, you will see that sometimes we have a value 1 as the product. For example, 2*3 mod 5 = 1. This means that 2 and 3 are also multiplicative inverses of one another mod 5.
Division itself is not something that is defined. But we might have a question like, "Twice a number equals 1 mod 5" or 2x=3 mod 5. In ordinary arithmetic, we would divide by 2. That doesn't exist. But we do have a multiplicative inverse, and we can multiply both sides by 3. This gives a new equation 3*2x = 3*3 mod 5 or x = 4 mod 5.(0 votes)
- I am wondering what this has too do with cryptography. Isn't it math?(1 vote)
- Most modern cryptography relies on modular arithmetic. Two notable example are RSA and Diffie Hellman.
Older ciphers like the Caesar cipher, Vigenere cipher, and Affine ciphers use it too.(2 votes)
- In terms of PEDMAS, doesn't modulus operations fall in the category of division/multiplication? Therefore, shouldn't (a mod c * b mod c) mod c be written like:
( ( a mod c ) * ( b mod c ) ) mod c?(1 vote)- (a mod c * b mod c) mod c is equivalent to ( ( a mod c ) * ( b mod c ) ) mod c
The brackets are implicit i.e. they do not have to be explicitly shown.(1 vote)