1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.