Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Have you heard of the square and multiply algorithm? It may be useful in this situation. –  Henrik Finsberg Apr 8 '13 at 18:11
1  
    
Fermat's little theorem –  Noturab Apr 8 '13 at 18:29

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.