I have a plaintext to be decrypted as follows:
$m = 2^{953} \bmod 1147$.
However, when I type $2^{953}$ in the calculator it gives me a math error!
So, how can I solve this equation? Even though, I couldn't find an answer for this on the Internet.
The answer should be $721$.
One very fast way for a computer to do this is to use Fast Modular Exponentiation (FME). Python has a built-in function named "pow" to do this (thanks to kelalaka for this!), where
solves the problem $A^B \mod C$. You can also find websites which do FME like https://www.dcode.fr/modular-exponentiation for example. Both my code and that website's code were able to find the answer just a second or two. The math behind FME is based on the nice property of Modular Arithmetic that $$xy \text{ mod } z = (x \text{ mod } z)(y \text{ mod }z).$$ Specifically, the way that my code works is that it splits 953 into the sum of powers of 2, i.e. $$953 = 2^9 + 2^8 + 2^7 + 2^5 + 2^4 + 2^3 + 2^0,$$ so then $$ 2^{953} = 2^{2^9 + 2^8 + 2^7 + 2^5 + 2^4 + 2^3 + 2^0} $$ which is $$ 2^{953} = 2^{2^0} \cdot 2^{2^3} \cdot 2^{2^4} \cdot 2^{2^5} \cdot 2^{2^7} \cdot 2^{2^8} \cdot 2^{2^9}. $$ For a human this doesn't look easy but for a computer it is efficient since $(a^{2^b})^2) = a^{2^{b+1}}$, so the computer can just remember the last thing it computed and just square it. Hope this helps!