# RSA Decryption of a huge cipher text and exponent

I am trying to work an assignment question I have been stuck on for some time.

The question is to decrypt the message with given decryption key and mod $n$.

$$374484638351^{320986308343} \bmod 374485250303$$

Now using a math software I get the message to be $374484638351$ which is the exact same as the cipher text.

the problem is though for the assignment I must write this all on paper without using any softwares. The only thing i am allowed to use software ofr is long division or multiplication. I have tried numerous methods to try and solve this but have been unsuccessful. One hint was that $(m-1)^2= 1 \bmod m$

I have NO intention of doing repeated squaring on paper by hand of such a LARGE number so I have been trying to reduce that exponent somehow but there is something I am missing or not seeing that is preventing me from reducing that huge exponent.

I have also tried to use that hint given to me $(m-1)^2= 1 \bmod m$ to reduce the cipher text but that didnt work.. someway or somehow I am guessing we have to use that hint to simplify this but dont know how

-

## 1 Answer

Since the modulus is the same as your previous question I assume you have the prime factors

$$374485250303 =611951\times 611953.$$

By the Chinese Remainder Theorem it suffices to compute the exponentiation modulo $p$ and $q$ first separately. The remainders we compute with long division are

$$374484638351\equiv -1 \mod 611951$$

$$374484638351\equiv 1 \mod 611953$$

Now since the decryption key 320986308343 is odd we know that the message has the same exact residues as above (taking $-1$ and $1$ to odd powers changes nothing): since the residues uniquely determine a number modulo $n$ we know the message is the exact same number as the ciphertext!

-
thanks once again anon, question though, how did you get the remainder as -1 or 1 when you mod the cipher text? and is it possible to elborate a tiny bit more on that last line residues is a little weakness for me – Raynos Mar 5 '12 at 10:58
Raynos: You said software was allowed for long division, so I used Wolfram|Alpha. The first actually spat back 611950, but the key is to notice this is the same as -1 modulo 611951 because it is exactly one less. | Look up CRT on Wikipedia or search around; if we have residues of $x$ modulo a set of pairwise coprime numbers, then $x$ is determined uniquely modulo the product of those numbers. Here that means if $x=a$ mod $p$ and $x=b$ mod $q$ then there is precisely one solution $x$ mod $pq$. This implies the message and cipher can be none other than the same, as they share the same residues. – anon Mar 5 '12 at 11:05