$16=m^{19} \mod 143$ - what is $m$

Question

The background is RSA encryption. Can I use some theorem to exploit this situation?

I thought about fermats theorem but I don t know how to use it here

fermats theorem (If a and p are coprime numbers such that $a^{p−1} − 1$ is divisible by p, then p need not be prime.)

Answer 1

Hint:

We can't apply Fermat's theorem because $143 = 11 \cdot 13$ is not prime. But we can apply it to the prime factors: $$ m^{10} \equiv 1 \bmod 11, \quad m^{12} \equiv 1 \bmod 13 $$ Thus, solve $19x \equiv 1 \bmod 10$ and $19x \equiv 1 \bmod 12$. Then $m = m^1 \equiv m^{19x} \equiv 16^x \bmod 143$.

Answer 2

You've got a case of RSA encryption, using $n=143$ and $e=19$. As $n=13 \times 11$, $\phi(n)=2 \times 10=120$ so we need to invert $19$ modulo $120$ to find $d$.

Extended Euclid for $19$ and $120$ gives us that

$$-3 \times 120 + 19\times 19 = 1$$

so that $$d=19^{-1}\pmod{120}=19$$.

So $m=16^{19} \pmod{143}= 42$