Properties of modulus algebra

In summary, the conversation discusses questions about the properties of RSA and Diffie-Hellman exchange, specifically in relation to the modulus math they are based on. The conversation touches on topics such as Fermat's Little Theorem, the commutative, associative, and distributive properties, and the homomorphism property of modulo. It also clarifies the difference between the modulus operator in computing and in mathematics. The conversation concludes with an explanation of the notation used in the Diffie-Hellman exchange and how it relates to the properties discussed.
  • #1
140
6
I'm trying to better understand RSA and Diffie-Hellman exchange and the modulus math that they are base on, there are some questions I have about there properties for which I am unable to find concise explanations about. I'm generally interested in how the commutative, associative, distributive, etc.. properties apply.
Questions 1. About Fermat's Little Theorem.

MP-1 ≡ 1 (mod P) which I'm told implies that...
MP ≡ M (mod P)

Is this essentially multiplying by M on both sides?? So if X ≡ Y ( mod P) then aX ≡ aY (mod P) ?

Does. a⋅[ X (mod P)] = aX (mod P) is it a⋅[ X (mod P)] = the remainder of X/P times a ?

Also in the Diffie Hellman exchange I'm told that...

(ga mod p)b (mod p) = gab (mod p)

which i think means in general that...

[ g (mod p)]a (mod p)= ga ( mod p )

but I'm not sure what property that uses. Can that be derived from the multiplication property where...

ab ( mod p ) = [ a (mod p) ⋅ b (mod p) ] (mod p)

Thanks a lot for any explanation you can give to point me on the right track.
 
Mathematics news on Phys.org
  • #2
The answer to your questions is basically the homomorphism property of modulo.
Let ##φ(a) = r## if ##a = k \cdot M +r##, i.e. ##φ =\mod(M)##. Then if ##b = l \cdot M + q## we get

## φ(ab) =##
##= ab\mod(M)##
##= ((k \cdot M + r) \cdot (l \cdot M+q))\mod(M)##
##= ((klM + rl +qk) \cdot M + rq)\mod (M)##
##= rq##
##= (a\mod(M)) \cdot (b\mod(M))##
##= φ(a) \cdot φ(b)##
 
  • #3
FrankJ777 said:
Does. a⋅[ X (mod P)] = aX (mod P) is it a⋅[ X (mod P)] = the remainder of X/P times a ?
In computing, the modulus operator takes the remainder after division. In mathematics it is something quite different. The modulus notation modifies the equality test.

When we write "a = b (mod P)" that should be understood to mean that a and b are equivalent modulo p. That is to say that they have the same remainder when divided by p.

When the (mod P) notation appears to the left of the equal sign, it amounts to mathematical nonsense.
 
  • #4
Fresh, sorry I haven't taken abstract algebra. Please tell me if I'm understanding you correctly.
fresh_42 said:
The answer to your questions is basically the homomorphism property of modulo.
Let ##φ(a) = r## if ##a = k \cdot M +r##, i.e. ##φ =\mod(M)##. Then if ##b = l \cdot M + q## we get

## φ(ab) =##
##= ab\mod(M)##
...
##= (a\mod(M)) \cdot (b\mod(M))##
##= φ(a) \cdot φ(b)##
You are saying that φ(a) is the function a (mod M). ?
And that..

ab (mod M) = a (mod M) ⋅ b (mod M)

from most other things I've read the identity is...

ab (mod M) = ( a (mod M) ⋅ b (mod M) ) (mod M)

Am I understanding you correctly?
 
  • #5
jbriggs444 said:
In computing, the modulus operator takes the remainder after division. In mathematics it is something quite different. The modulus notation modifies the equality test.

When we write "a = b (mod P)" that should be understood to mean that a and b are equivalent modulo p. That is to say that they have the same remainder when divided by p.

When the (mod P) notation appears to the left of the equal sign, it amounts to mathematical nonsense.

OK. How do I interpret the expression?
If i multiply a number time a modular expression such as...
a⋅[ X (mod P)]
is it the same thing as saying...
= aX (mod P)
or is it a⋅[ X (mod P)] = the remainder of X/P times a
 
  • #6
FrankJ777 said:
Fresh, sorry I haven't taken abstract algebra. Please tell me if I'm understanding you correctly.

You are saying that φ(a) is the function a (mod M). ?
And that.
Yes.
ab (mod M) = a (mod M) ⋅ b (mod M)
Correct.
from most other things I've read the identity is...

ab (mod M) = ( a (mod M) ⋅ b (mod M) ) (mod M)

Am I understanding you correctly?
Yes. The first three mod's here mean to take the remainder and the last isn't really necessary (only if programming). The last one only tells in which number area the second multiplication took place, namely in the domain of possible remainders of (division by) ##M.##

I does not matter how often or where you take the remainder. And ##\mod M## is simply that: the remainder if divided by ##M##.
As jbriggs444 has said: ##a ≡ b \mod M## means just that ##a## and ##b## have the same remainder when divided by ##M##, or ##(a-b)## is divisible by ##M.##
Your notation with the many mod's in between is somehow computer language to keep the numbers short. It makes not really a difference.
 
  • #7
FrankJ777 said:
OK. How do I interpret the expression?
If i multiply a number time a modular expression such as...
a⋅[ X (mod P)]
This doesn't make much mathematical sense, because one doesn't know where you multiply.
If you multiply integers and take the remainder afterwards, ok, like ##3 \cdot 6 = 18 = 6 \mod 12##. But this is a different multiplication from what you do on the remainders. E.g. ##3 \cdot 4 = 0 \mod 12##. You don't get zero on the integers, only after passing to the remainders. So in your expression it's not clear where you want to multiply, even if you might get the same result as intended. It's simply a dirty notation.
If you want to be precise you could use ##≡## instead of ##=## to signal that all arithmetic operations are performed on the remainders only.
 
  • #8
OK. At this page explaining the math behind Diffie-Hellman they state:

(ga mod p)b mod p = gab mod p
(gb mod p)a mod p = gba mod p


I believe in this example they intend the ' = ' to mean exactly equal, not equivalent congruent. Also I think the additional (mod p)'s in red make the remainder on both sides exactly equal. Does this make mathematical sense in this context?

So is it a general rule that...

(g mod p)b mod p = gb mod p
or that...
(g mod p)b ≡ gb mod p

Can this be derived from the multiplication property?
Thanks.
 
  • #9
jbriggs444 said:
The modulus notation modifies the equality test.

Should we say that the modulus notation also modifies the meaning of everything in an equation?

For example, does the expression: [itex](3)(4) mod(5) [/itex] use "3" to denote an integer or does it use "3" to denote an equivalence class of integers, in which case "3" denotes a set ? Or perhaps "3" denotes an integer, but the integer is a "representative" for a set ?
 
  • Like
Likes jbriggs444
  • #10
Stephen Tashi said:
Should we say that the modulus notation also modifies the meaning of everything in an equation?
Perhaps so. I've never worried about it much since things works out the same under either interpretation.
 
  • #11
Stephen Tashi said:
Should we say that the modulus notation also modifies the meaning of everything in an equation?

For example, does the expression: [itex](3)(4) mod(5) [/itex] use "3" to denote an integer or does it use "3" to denote an equivalence class of integers, in which case "3" denotes a set ? Or perhaps "3" denotes an integer, but the integer is a "representative" for a set ?
I think it is all about the where. Where do you calculate in? You can do all arithmetic in ##ℤ## and project the result onto ##ℤ/nℤ## or you can forget about ##ℤ## and the cosets and consider ##ℤ/nℤ## as the ring to perform the calculations in: no more cosets, representatives or integers, simply different rules. Confusion only arises if one messes up the two concepts and switch between them. As ##ℤ → ℤ/nℤ## is a ring homomorphism it doesn't really matter concerning the results. However, it is kind of dirty.
 
  • #12
FrankJ777 said:
OK. At this page explaining the math behind Diffie-Hellman they state:

(ga mod p)b mod p = gab mod p

Is it [itex] (g^a\ mod\ p)^b\ mod\ p [/itex] ?
 
  • #13
Stephen Tashi said:
Is it [itex] (g^a\ mod\ p)^b\ mod\ p [/itex] ?

Yes Stephen. My bad. Let me repost this.

(ga mod p)b mod p = gab mod p
(gb mod p)a mod p = gba mod p


Thanks
 

1. What is the definition of modulus algebra?

Modulus algebra, also known as congruence algebra, is a branch of mathematics that deals with the properties of congruence equations, which are equations that involve the modulus operator (%).

2. What are the basic properties of modulus algebra?

The basic properties of modulus algebra include the commutative, associative, and distributive properties, as well as the property of cancellation.

3. How is modulus algebra used in real life?

Modulus algebra has many practical applications, such as in cryptography, computer science, and engineering. It is also used in everyday situations, such as calculating discounts and finding remainders in division problems.

4. What is the difference between modulus algebra and regular algebra?

The main difference between modulus algebra and regular algebra is the use of the modulus operator (%). In regular algebra, all operations are performed using real numbers, while in modulus algebra, all numbers are treated as congruent numbers with respect to a given modulus.

5. What are some common mistakes when working with modulus algebra?

Some common mistakes when working with modulus algebra include forgetting to specify the modulus, confusing the modulus operator with division, and incorrectly applying the distributive property. It is important to carefully follow the rules of modulus algebra to avoid these errors.

Suggested for: Properties of modulus algebra

Replies
22
Views
256
Replies
7
Views
1K
Replies
5
Views
1K
Replies
44
Views
3K
Replies
3
Views
748
Replies
4
Views
671
Replies
1
Views
672
Replies
1
Views
837
Replies
3
Views
620
Back
Top