# Find the modulo between two large number

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

• Have you heard of the square and multiply algorithm? It may be useful in this situation. Commented Apr 8, 2013 at 18:11
• Exponentiation by repeated squaring. Commented Apr 8, 2013 at 18:13
• Fermat's little theorem Commented Apr 8, 2013 at 18:29

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