How to calculate the mod value of a rational/irrational value?

Question

We have a course in network security this semester and we are being taught RSA algorithm.

I came across a typical math problem that I was unable to solve here.

$$D*E \equiv 1 \mod{\phi(n)}$$

This became $$D \equiv E^{-1} \mod{\phi(n)}$$ How do you solve this ???

My lect gave this specific example

$$D \equiv 7^{-1} \mod{160}$$ and the solution for $D$ was $23$! How did she arrive at this.

To have your Latex render, enclose it in dollar signs $. – Nov 20 '13 at 02:41 — , Nov 20 '13 at 02:41

score 0 · Answer 1 · answered May 30 '16 at 01:59

D ≡ (mod 160)/7 which is equal to 7D ≡ 1 * (mod 160)

This type of question is a Congruence Relation.

This means that (1 mod 160) = (7D mod 160)

(1 mod 160) simplifies to 1 so that means that (7D mod 160) = 1

This means that 7D/160 must have a remainder of 1

You know that 1 is a possible answer but that would create a decimal when divided by 7 and RSA numbers do not do decimals.

The equation will usually get the number just above but also closest to the modular divisor which in this case is 160+1 or 161.

161/7 = 23

score 0 · Accepted Answer · answered Nov 20 '13 at 02:44

0

Hint

$7D = 1 \mod 160$

Sol'n

$7D = 1 \mod 160$ and $D = 23 \Longrightarrow 23*7 \mod 160$ satisfies this.

answered Nov 20 '13 at 02:44

Don Larynx

4,703

I know 23 satisfies the equation :| I wanted to know how did she arrive at 23. Is there a non trial and error way of solving this ? – user2340452 Nov 20 '13 at 02:54
HINT: Divide 160 by 7 in the integer ring. – Don Larynx Nov 20 '13 at 02:56

score -1 · Answer 3 · answered May 22 '18 at 18:53

-1

https://www.youtube.com/watch?v=mgvA3z-vOzc Check this out. The problem can be solved using extended Euclidean Algorithm to be precise. For smaller numbers, the answers already mentioned are sufficient.

answered May 22 '18 at 18:53

Sherwin

1

How to calculate the mod value of a rational/irrational value?

3 Answers3