Trouble understanding modulo equivalence notation

In summary, the conversation discusses the understanding of RSA and modular math, specifically the encryption function y ≡ xe (mod n). The question arises whether y should be interpreted as the remainder of xe/n or a number that when divided by n has a remainder equal to the remainder of xe divided by n. The values for the integer plain text and cipher text are also mentioned, along with the confusion about the numbers 310, 132, and 189 in the example. The conversation concludes with a request for clarification on the meaning of y ≡ xe (mod n) and where the red numbers in the example come from.
  • #1
140
6

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:
Physics news on Phys.org
  • #2
FrankJ777 said:

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:

1. What is modulo equivalence notation?

Modulo equivalence notation is a mathematical concept used to describe the relationship between two numbers, where the remainder of the division of one number by another is equal. It is denoted by the symbol "≡" and is read as "is congruent to."

2. How is modulo equivalence notation used in science?

Modulo equivalence notation is commonly used in science to represent cyclic patterns, such as in the study of repeating patterns in chemical reactions or oscillations in physical systems. It is also used in cryptography to ensure secure communication by encoding messages using modulo arithmetic.

3. What is the difference between modulo equivalence notation and regular equivalence?

The main difference between modulo equivalence notation and regular equivalence is that modulo equivalence considers the remainder of the division between two numbers, while regular equivalence looks at the equality of the two numbers themselves. For example, 10 ≡ 2 (mod 4) is true because the remainder of 10 divided by 4 is 2, while 10 = 2 is false.

4. How do I solve problems involving modulo equivalence?

To solve problems involving modulo equivalence, you must first determine the value of the modulo (denoted by "mod") and then use basic arithmetic operations to find the remainder of the division between the two numbers in question. Remember to use the modulo symbol "≡" to denote the relationship between the two numbers.

5. Can modulo equivalence notation be applied to non-numeric values?

Yes, modulo equivalence notation can also be applied to non-numeric values, such as letters or symbols. In this case, the modulo operation would involve converting the values to their corresponding numerical equivalents and performing the calculation using those numbers. This can be useful in coding and encryption algorithms.

Suggested for: Trouble understanding modulo equivalence notation

Replies
2
Views
965
Replies
2
Views
831
Replies
3
Views
900
Replies
3
Views
1K
Replies
3
Views
888
Replies
4
Views
1K
Replies
1
Views
1K
Replies
16
Views
1K
Back
Top