1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trouble understanding modulo equivalence notation

  1. May 20, 2016 #1
    1. The problem statement, all variables and given/known data
    I'm trying to understand RSA and modular math better. I've studied some of the relations and rules, but I keep getting stuck when i try to follow an example all the way through. I'm also getting confused by how I'm supposed to treat ≡ vs = at some times. Here is the background in this particular example:

    The encryption function is y ≡ xe (mod n), where x is the integer value of the plain text and y the integer value of the cipher text.
    I'm not sure if this means: y = xe (mod n), meaning y = the remainder of xe/n or should i interpret it to mean:
    y (mod n) ≡ xe (mod n) where i should solve for y, so that the remainder of y/n = the remainder of xe/n ?

    Would I do that using the Chinese remainder theorem or Euclid algorithm? or the relationship y = xe (mod n): ⇒ y-x/m = k ?



    2. Relevant equations
    In this example: e = 11, p = 13 , q = 29 and n = pq = 377. Φ(n) = (p-1)(q-1)= 336.
    the values for the integer plain text is 110, 111, 119. Y is the cipher text.

    y ≡ 11011310 (mod 377)
    y ≡ 11111132 (mod 377)
    y ≡ 11911189 (mod 377)


    What does y equal, and where did the numbers 310, 132, 189 (in red) come from??
    According to the example the cipher text is 310, 132, 189.

    Here is a hyperlink to the entire example. http://math.gcsu.edu/%7Eryan/12capstone/papers/maxey.pdf [Broken]
    3. The attempt at a solution

    So now I'm confused. Considering the first line of the relevant equations...
    Is it saying
    y = 110 11 ( mod 377) = 310, and ⇒ y ≡ 310 (mod 377) ⇒ y (mod 377) = 310 (mod 377) ???

    if I calculate 110 11 (mod 377) does not equal 310 (mod 377)...
    110 11 ( mod 377) = 28531167061100000000000 (mod 377) = 372
    and 310 (mod 377) = 310.

    So where does the number 310 come from??
    According to the example y is the cipher text, and the cipher text is 310, so how do we find y.
    Are we supposed to find y through the relationship..
    y ≡ 11011 (mod 377)
    y (mod 377)
    11011 (mod 377)
    Then we solve for y using anther method and come up with y = 310.

    So, to recap...
    1) Does y ≡ xe (mod n) mean find y for y (mod n) = xe (mod n) ?? In other words is the cipertext y, the remainder of xe (mod n) or is it a number that when divided by n has a remainder equal to the remainder of xe divided by n.
    2) Where did the red numbers (310, 132, and 189) come from in the example. Are these equal to the y's??

    I would like to work through this by myself as much as possible, but I'm stuck and thoroughly confused.
    Thanks for the help guys.
     
    Last edited by a moderator: May 7, 2017
  2. jcsd
  3. May 20, 2016 #2

    fresh_42

    Staff: Mentor

    ##a ≡ b \, (mod \, n)## means, that by division with ##n## both ##a## and ##b## have the same remainder, i.e. ##a - b## is divisible by ##n.##
    Thus we can write it as an equation ##a = k \cdot n + b## for some integer (!) ##k##.
    ##a ≡ b \, (mod \, n)## is sometimes also written ##a ≡ b \, (\, n)##

    I don't know why you want to find something. It simply means division by ##n## gets the same remainder for ##y## and ##x^e##.

    Yes. As long as you accept all remainders ##k \cdot n + y## for we can't know whether ##y## is already the smallest one possible. Usually it is. But ##23 ≡ 1 (mod \, 2)## is also true because the division of ##23## by ##2## gets ##1## as remainder.

    Yes.

    Calculate ##110^{11}##, divide it by ##377##, subtract the integer part and multiply the rest by ##377## to get the remainder, which is ##310##. The other two can be found in the same way.
     
    Last edited by a moderator: May 7, 2017
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: Trouble understanding modulo equivalence notation
  1. Modulo 2 long division (Replies: 1)

Loading...