# Decode the following message which was sent using mod m=7081 and exponent k=1789 (RSA)

Decode the following message which was sent using mod $m = 7081$ and exponent $k=1789$ (RSA): $$5192 2604 4222$$ I solved $\phi(7081)=6912$, and then solved the linear equation $1789u-6912v=1$ where $u=85$ and $v=22$.

But then, when I plugged this into $5192^85 \mod 7081$, successive squaring gave me $0$. Clearly incorrect.

I got: $$85=2^0+2^2+2^4+2^6$$ $$5192^1=5192 \pmod{7081}\\ 5192^2=6578 \pmod{7081}\\ 5192^4=5174 \pmod{7081}\\ 5192^8=0 \pmod{7081}$$ I also got the other two numbers $(2604, 4222)$ raised to the $8$th power are congruent to $0$. Where did I go wrong in this problem?

-
What are you using to calculate this? $5192^8 \equiv 4096 \pmod {7081}$ – Brandon Carter Apr 10 '11 at 16:19
Specifically, your last step is wrong; $5192^4 \equiv 5174$, but then $5192^8 \equiv 5174^2 \not \equiv 0$. – Zach Langley Apr 10 '11 at 16:25
@Joseph: Wolfram Alpha gives the correct answer: wolframalpha.com/input/?i=5192^8+mod+7081 – Brandon Carter Apr 10 '11 at 16:26
@Joseph, I just plugged in exactly that and it gave the correct answer: wolframalpha.com/input/?i=4222%5E%282%5E3%29+mod+7081 – Zach Langley Apr 10 '11 at 16:54
Better yet for entering into Wolfram Alpha: PowerMod[4222, 2^3, 7081] – J. M. Apr 10 '11 at 17:22

You did it right, in that $d=85$ is the decryption exponent, as $d$ and $e = 1789$ are inverses modulo $\phi(n) = \phi(7081) = 6912$. Entering 5192 ** 85 % 7081 in python, I get 1615, which seems like 2 letters (using A = 1, etc in a digraphic code). Also the other 2 groups give 2823 and 1130, which seems to imply some extra characters besides just letters. Wolfram alpha agrees (entering 5192^85 mod 7081 etc.)