The Mathematics of ElGamal

The version of the ElGamal cryptosystem also relies on modular arithmetic.

ElGamal public keys

Recall that each ElGamal public key involves three numbers. The first is a prime $p$, while the second number $g$ has the special property of a primitive element. We’ll now explain the significance of this.

Primitive elements

Let $p$ be a prime. A number $g$ between 1 and $p - 1$ is said to be primitive (or is a primitive element) modulo $p$ if the numbers:

$$g, g^2, g^3, g^4, g^5, g^6, ... , g^{p-1} \; mod \; p$$

are all different. If this is the case, since there are $p - 1$ of them, they must consist of $1, 2, 3, ... , p - 1$ in some order.