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
Best 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!