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