Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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!

share|cite|improve this answer
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

Your Answer


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.