How to solve an exponential ciphers?

[sachiyo]

p=2633 , C=423 , e=29

plain text: EX (0423)
how to solve 423^29 mod 2633 without using calculator?

 

[Hurkyl]

You only need 28 multiplies to do it in the most obvious fashion. *shrug* I bet you've learned a better way to do it if you read your notes / text.

 

[sachiyo]

There is some hints to do it by using Euler's theorem. But I still have no idea to do it.

 

[Gokul43201]

it's painstaking

For standard RSA type encryption, the number N = 2633 (public key) is a product of 2 primes, p and q, which allows for decription using (p-1) and (q-1). However, in your choice, N is 2633 which itself is prime, and so does not allow for easy decription (also it is not the 29th Merseene Prime, or suchtypes). Anyway, there is a general approach to solve your problem...in this particular case, the numbers appear to conspire to giving large remainders with most powers I tried. I actually solved your problem without a calculator, and it took me about 1 hour, cause it's mostly "brute force" arithmetic. Here's how I did it :

Notation : a^e||p==x means that x is the residue when 'a' raised to the e'th power is divided by p.
Note : use (a^e)(b^f)||p==[(a^e||p)(b^f||p)] ||p and (a^e + b^f)||p==[(a^e||p) + (b^f||p)] ||p

423 = (3^2)*47, already a bad start ...stuck with a bg prime, 47.
So, 423^29 = (3^58)*(47^29)
3^8||2633=6561||2633==1295, which is large and unwieldy, 3^9, 3^10 & 3^11 also give large remainders so i tried 47*3^7||2633 ==102, a relatively small number, and close enough to 100 that it is easy to square and cube easily. Of course, using this, we will exhaust the 3's way before work through the 47's but that is a small price.

So, (47^2)*(3^14)||2633==102^2||2633 = 10404||2633 = 2505, yikes, that didn't help very much.
Fortunately it's not hard to square 2505. [2505^2 = 2500^2 + 25 + 25000=6250000+25025]
So, (47^4)*(3^28)||2633==2505^2||2633==6275025||2633==586 (have to do long division !)
We still need (47^25)*3||2633 to get the answer. Let's hack away at those 47's now...
47^3||2633 == 103823||2633 == 1136
So 47^4||2633==1136*47||2633==53392||2633==732
and 47^5||2633==732*47||2633==34404||2633==175, a nice, small number, hooray !
47^10||2633==175^2||2633 = 30625||2633==1662, bah !
So, that's all tha patience I've got, but you must get the idea by now. If you get a small remainder, you can square or cube; if it's large, you multiply by 47 and continue...

WOW, what a mindless calculation to do. I was curious to see if the result would be 1 or 0, or something interesting...but it wasn't. I hope someone doesn't follow up with a 3-step claculation that gives the answer !