1

I'm trying to work through the math behind public key encryption, I'm a computer programmer, but not a mathematician. I came across this wonderful example, but I'm confused about the use of (mod x) my understanding of modulus is that it is the remainder after devision. e.g. 5 % 2 = 1. but this is odd:

rs ≡ 1 (mod m) where r = 3, s = 59 and m = 176

how can s = 59 my understanding is that 1 mod 176 would be 1.

Fire Crow
  • 113

2 Answers2

2

Note that $rs = 3(59)= 177 = 176+1 \equiv 1 \pmod{176}$.

To find $s$, we usually use euclidean algorithm.

$$176 = 58(3)+2$$ $$3 = 2(1) + 1$$

Hence

\begin{align} 1 &= 3-2(1) \\ &=3-(176-58(3)) \\ &= 59(3)-176 \end{align}

Hence $$1 \equiv 59(3) \pmod{176}$$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Thank you, i don't completely understand, but i think the pieces outlined are enough for me to work off of. – Fire Crow Mar 20 '18 at 15:10
  • modulo arithmetic is like a clock, in this case, it is a clock with $176$ marks, when we see $176$, we can treat it as $0$. – Siong Thye Goh Mar 20 '18 at 15:12
1

You should know that $a \equiv b (\text{mod $m$)}$ means that $a-b$ is divisible by $m$.

For this modulo, you should note that $0$ is divisible by all positive natural numbers (result would be $0$), so $1$ when divided by any positive natural numbers (except $1$) will have $1$ as a remainder $\Rightarrow 1 \equiv 1 (\text{mod $m$)}$.

For this problem, $177$ when divided by $176$ will have a remainder of $1$, or $177-1$ is divisible by $176$ $\Rightarrow 3 \times 59 \equiv 1 (\text{mod $176$)}$.

user061703
  • 3,877