I'm trying to find
3185^2753 mod 3233
to decode a RSA message. How can I do it? What is the theorem behind this, if any?
The original question is:
What is the original message encrypted using the RSA system with n=53·61 and e=17 if the encrypted message is
3185 2038 2460 2550? (To decrypt, first find the decryption
exponent d, which is the inverse of e=17 modulo 52·60.)
Best Answer
Hints without many words (arithmetic modulo $\,53\,,\,61\,$, Fermat's Little Theorem...):
$$3233=61\cdot 53$$
$$3185=13\pmod {61}\;,\;\;3185=5\pmod {53}\;,\;2753=61\cdot 45+8\;,\;\;2753=53\cdot 52-3$$
$$\implies 3185^{2753}=\left(13^{61}\right)^{45}\cdot 13^8=13^{53}=\left(13^3\right)^{17}\cdot 13^2=1\cdot169=47\pmod{61}$$
$$3185^{2753}=\left(5^{53}\right)^{52}\cdot 5^{-3}=5^{-3}=\left(5^{-1}\right)^3=32^3=14\pmod{53}\ldots$$