The Mathematics of ElGamal

Let’s learn the basic mathematics behind 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 pp, while the second number gg has the special property of a primitive element. We’ll now explain the significance of this.

Primitive elements

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

g,g2,g3,g4,g5,g6,...,gp1  mod  pg, 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 p1p - 1 of them, they must consist of 1,2,3,...,p11, 2, 3, ... , p - 1 in some order.

Get hands-on with 1200+ tech skills courses.