# How to compute ElGamal decryption by hand

Lets say that $$u=3, x=5, v=2$$, how do we work out $$u^{-x}*v$$, so $$3^{-5} * 2$$. I know how to work out the answer if it was $$3^5 * 2$$ but how do we do it with negative exponents?

• I added some formatting to your post - Please ensure I did not change the meaning (I had to assume the precedence for u^-x * v was $u^{-x} * v$ and not $u^{-x * v}$) – Ella Rose Aug 24 '19 at 15:05

We're not trying to compute $$3^{-5}\ast 2$$, but instead we're trying to compute $$3^{-5}\ast 2\mod p$$ for some prime $$p$$. This is notation for $$(3^{-1})^5\ast 2\mod p$$, so if we can compute what $$3^{-1}\mod p$$ is, you can just plug that value in and do computations like you'd expect. Note that $$3^{-1}\mod p$$ means the element $$u\in(\mathbb{Z}/p\mathbb{Z})^\times$$ such that $$u\ast 3\equiv 1\mod p$$. For example, because $$2\ast 2\mod 3 \equiv 1\mod 3$$, we have that $$2^{-1} \mod 3= 2$$. Or, because $$2\ast 3\equiv 1\mod 5$$, we have that $$2^{-1}\mod 5\equiv 3$$. The quantity $$u^{-1}$$ ends up being uniquely defined (when it exists --- $$2\ast 3\equiv 0\mod 6$$ means that $$2^{-1}\mod 6$$ can't exist), but note that it depends on both $$u$$ and $$p$$.
A computationally inefficient (but conceptually simple) way to compute $$3^{-1}$$ is via Fermat's Little Theorem, which states that:
If $$a\in\mathbb{Z}$$, then $$a^p\equiv a\mod p$$
If $$a\neq 0$$, this is equivalent to $$a^{p-1}\equiv 1\mod p$$, and therefore $$a^{p-2}\equiv a^{-1}\mod p$$. So we can compute $$3^{-1}\mod p\equiv 3^{p-2}\mod p$$, which you can do by hand. If $$p$$ is large this might be annoying, but there are some tricks to speed it up (known as exponentiation by squaring).