• Support PF! Buy your school textbooks, materials and every day products Here!

Trouble understanding modulo equivalence notation

  • #1
129
2

Homework Statement


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 ?



Homework 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:

Answers and Replies

  • #2
12,692
9,235

Homework Statement


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 ?



Homework 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.
##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)##

1) Does y ≡ xe (mod n) mean find y for y (mod n) = xe (mod 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##.

In other words is the cipertext y, the remainder of xe (mod n)
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.

or is it a number that when divided by n has a remainder equal to the remainder of xe divided by n.
Yes.

2) Where did the red numbers (310, 132, and 189) come from in the example. Are these equal to the y's??
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:

Related Threads on Trouble understanding modulo equivalence notation

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
0
Views
2K
Replies
6
Views
584
  • Last Post
Replies
3
Views
115
Replies
1
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
0
Views
907
  • Last Post
Replies
1
Views
2K
Top