Given RSA encoding function $E: x\to x^7 \pmod{6161} $ find decoding function D

Question

So far I got:

$7\alpha \equiv 1$ mod $\phi(6161)$

$\phi(6161) = \phi(61) \times \phi(101) = 6000$
$7\alpha \equiv 1$(mod $6000)$

At this point we are supposed to do euclid's algorithm and somehow arrive at:

$D: x\to x^{5143}$ mod $6161$

I don't understand the euclid step

Answer 1

Start the Euclidean Algorithm. So we divide $6000$ by $7$. The quotient is $857$ and the remainder is $1$, that is, $$6000=(7)(857)+1.$$ Now the Euclidean Algorithm is over! We have reached a remainder of $1$. Thus $$1=(7)(-857)+6000.$$ So we have expressed $1$ as an integer linear combination of $7$ and $6000$. But we want the decoding index to be positive. So we want to replace $-857$ by a positive number congruent to $-857$ modulo $6000$. We have $-857\equiv 6000-857\pmod{6000}$. But $6000-857=5143$, so $$(7)(5143)\equiv 1 \pmod{6000}.$$ We have found the modular inverse of $7$ modulo $6000$. This is the decoding index.

In general, the Euclidean Algorithm takes substantially longer, so the back substitution process is not properly illustrated by this example.

Answer 2

If 7 is the exponent you use to encrypt, then $\alpha$ should decrypt. What is the inverse to 7 modulo 6000? This is where the Euclidean algorithm comes in.

Answer 3

Hint $\rm\ mod\ m = 1\!+\!7k\!:\,\ 1\equiv -7\,\color{#C00}k\ \Rightarrow\ \dfrac{1}7\,\equiv\, \dfrac{-7k}{\ 7}\, \equiv\, -\color{#C00}k$

Therefore $\rm\ m = 6000 = 1+ 7\cdot \color{#C00}{857}\ \Rightarrow\: \dfrac{1}{7}\,\equiv\, -\color{#C00}{857}\equiv 5143\pmod{6000}$

Generally one can employ the Extended Euclidean Algorithm to compute modular inverses. The above is an optimization for the frequent special case where the modulus is $\equiv \pm1\:$ modulo the number being inverted ($= 7$ above), so the algorithm terminates in a single step.