Question 1

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...?

Accepted Answer

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.

Question 2

Is there an intuitive explanation for modular multiplication (something involving clocks) like there is for modular addition?

Accepted Answer

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

Question 3

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) ?

Accepted Answer

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.

Question 4

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

Accepted Answer

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.

Question 5

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

Accepted Answer

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

Question 6

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?

Accepted Answer

*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

Question 7

I am wondering what this has too do with cryptography. Isn't it math?

Accepted Answer

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.

Computer science

Course: Computer science > Unit 2

Modular multiplication

Let's explore the multiplication property of modular arithmetic:

Example for Multiplication:

Proof for Modular Multiplication

Want to join the conversation?