$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.)

Fermat's theorem says $a^{p-1}$ is divisible by $p$ if $p$ is prime, but $143$ isn’t prime — J. W. Tanner, Jul 10 '20 at 13:20

lhf · Accepted Answer · 2020-07-10T13:37:40.140

2

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$.

edited Jul 10 '20 at 13:37

answered Jul 10 '20 at 13:23

lhf

216,483

I have calculated x=9 for the first equation and x = 11 for the second equation. How does this help me to calculate the last equation? Can you also tell me how you came up with this method? – New2Math Jul 10 '20 at 13:33
@New2Math: $x$ is not $11$ for the second equation. Try again. Then solve for $x$ using your knowledge of $x\bmod 10$ and $x\bmod 12$. – TonyK Jul 10 '20 at 13:35
Ohh can you guys please explain why $10$ and $12$ -- they are not even co-prime. Thanks. – Alexey Burdin Jul 10 '20 at 13:36
it was x=7 - how can I proceed? – New2Math Jul 10 '20 at 13:37
Okay I guess the solution is 19 but can you give me an explaination for that? – New2Math Jul 10 '20 at 13:49
how do you apply fermat to the prime factors? – New2Math Jul 10 '20 at 14:03
how did you get that 19? – New2Math Jul 10 '20 at 14:09
@TonyK $x=9$ for the first equation and $x=7$ for the second equation. If $x=19$ then both equations are true - do you know what $x$ is for the third equation? I really don t know but if you give me the answer I think I will understand – New2Math Jul 10 '20 at 14:50
@New2Math: You have solved $19x\equiv 1\bmod 10$ and $19x\equiv 1\bmod 12$. So where are you stuck? Is it the calculation of $16^x\bmod 143$? – TonyK Jul 10 '20 at 14:53
@TonyK yes - the last calculation - I don t know what the $x$ is – New2Math Jul 10 '20 at 14:54
Yes you do. Read your previous comment carefully. – TonyK Jul 10 '20 at 15:00
@TonyK I really don t know is it 19? – New2Math Jul 10 '20 at 15:04
@New2Math: Yes, of course. – TonyK Jul 10 '20 at 15:19

score 0 · Answer 2 · answered Jul 12 '20 at 21:51

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$

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

2 Answers2