Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Properties of modulus algebra

  1. May 27, 2016 #1
    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.
     
  2. jcsd
  3. May 27, 2016 #2

    fresh_42

    Staff: Mentor

    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)##
     
  4. May 27, 2016 #3

    jbriggs444

    User Avatar
    Science Advisor

    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.
     
  5. May 27, 2016 #4
    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..

    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?
     
  6. May 27, 2016 #5
    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
     
  7. May 27, 2016 #6

    fresh_42

    Staff: Mentor

    Yes.
    Correct.
    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.
     
  8. May 27, 2016 #7

    fresh_42

    Staff: Mentor

    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.
     
  9. May 27, 2016 #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.
     
  10. Jun 3, 2016 #9

    Stephen Tashi

    User Avatar
    Science Advisor

    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 ?
     
  11. Jun 3, 2016 #10

    jbriggs444

    User Avatar
    Science Advisor

    Perhaps so. I've never worried about it much since things works out the same under either interpretation.
     
  12. Jun 3, 2016 #11

    fresh_42

    Staff: Mentor

    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.
     
  13. Jun 3, 2016 #12

    Stephen Tashi

    User Avatar
    Science Advisor

    Is it [itex] (g^a\ mod\ p)^b\ mod\ p [/itex] ?
     
  14. Jun 4, 2016 #13
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Properties of modulus algebra
  1. Modulus and inequalities (Replies: 14)

  2. Modulus integration (Replies: 9)

  3. Modulus of a tensor (Replies: 1)

Loading...