# What is meant by this notation in the ElGamal key generation process?

Alice chooses

i) A large prime $$p_A$$ (say 200 to 300 digits)
ii) A primitive element $$\alpha_A$$ modulo $$p_A$$,
iii) A (possibly random) integer $$d_A$$ with $$2 \le d_A \le p_A-2$$.

Alice computes

iv) $$\beta_A \equiv \alpha_A^{d_A} \pmod {p_A}$$.

Alice's public key is $$(p_A,\alpha_A,\beta_A)$$. Her private key is $$d_A$$.

What is meant by the notation $$\alpha_A$$, $$p_A$$, and what is meant by a 'primitive element', does it mean a small number or something else entirely?

• What do you mean by "a (subscript a)"? There is no a with a subscript anywhere in the quote? Do you mean $\alpha_A$? – CodesInChaos Jun 26 '13 at 10:09

## 1 Answer

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on.

A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, \alpha_A, \alpha_A^2, \alpha_A^3, \ldots, \alpha_A^{p_A-1}\}$ must be the whole set $\{1, 2, 3, \ldots, p-1\}$ of nonzero elements of the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, i.e. any nonzero element of the field can be expressed as a power of $\alpha_A$. Another way of expressing this property is that $\alpha_A$ must have the order $p-1$ (the largest possible order of an element of the field), which means that none of the $\alpha_A^k$ for $1 \le k \le p-2$ are equal to $1$ modulo $p$.