# How do I compute the huge numbers which occur in el gamal decryption?

I'm trying to do decryption using el gamal. The formula to get the message M is $$M=\frac{b}{a^x} mod \:P$$ In one case, we may have $$M=\frac{18}{62^{62}} mod \: 71$$ This value cannot be computed on a calculator as $62^{62}$ gives an infinite value. How do we get the value of M?

Two techniques will be of use here and in many similar problems. To find $(1/a)^b\pmod n$,
1. First, compute $1/a = a^{-1}\pmod n$. In your example, compute $62^{-1}\pmod{71}$, namely, the modular inverse of $62\pmod{71}$. That happens to be $63$.
2. Then use repeated squaring to find $(1/62)^{62}\equiv63^{62}\pmod{71}$, which will be 8. This relies on the fact that $a^{62} = a^{32+16+8+4+2}=(a^{32})(a^{16})(a^{8})(a^{4})(a^{2})$ where, reading from the right, each value is the square of the preceding one, meaning that you can find $a^{62}$ using 9 modular multiplications, rather than 61.