Editing ElGamal encryption (section)

=== Decryption ===
Alice decrypts a ciphertext <math>(c_1, c_2)</math> with her private key <math>x</math> as follows:
* Compute <math>s := c_1^x</math>. Since <math>c_1 = g^y</math>, <math>c_1^x = g^{xy} = h^y</math>, and thus it is the same shared secret that was used by Bob in encryption.
* Compute <math>s^{-1}</math>, the inverse of <math>s</math> in the group <math>G</math>. This can be computed in one of several ways. If <math>G</math> is a subgroup of a multiplicative group of integers modulo&nbsp;<math>n</math>, where <math>n</math> is prime, the [[modular multiplicative inverse]] can be computed using the [[extended Euclidean algorithm]]. An alternative is to compute <math>s^{-1}</math> as <math>c_1^{q-x}</math>. This is the inverse of <math>s</math> because of [[Lagrange's theorem (group theory)|Lagrange's theorem]], since <math>s \cdot c_1^{q-x} = g^{xy} \cdot g^{(q-x)y} = (g^{q})^y = e^y = e</math>.
* Compute <math>m := c_2 \cdot s^{-1}</math>. This calculation produces the original message <math>m</math>, because <math> c_2 = m \cdot s</math>; hence <math>c_2 \cdot s^{-1} = (m \cdot s) \cdot s^{-1} = m \cdot e = m</math>.
* Map <math>m</math> back to the plaintext message <math>M</math>.