# What is a generator?

I am trying to read up on the math behind DH and ran into the word generator used a lot. I am not sure what it means. Can someone explain?

I see this question where the OP talks about g as the generator. The accepted answer does not make me understand what a generator is. I always thought g is just a large prime in group. What is the generator and how is it different from the DH parameters?

-
Look up 'generator of a cyclic group' –  figlesquidge May 15 at 21:32

A generator of a finite group is a value $g$ such that all elements of the group can be represented as $g^k$ for some integer $k$. Another key of looking at it is that if we consider the sequence $g,\ \ g \cdot g,\ \ g \cdot g \cdot g, ...$, saying $g$ is a generator means that all values in the group will appear somewhere in the sequence.

Now, when it comes to Diffie-Hellman, generator is used in two slightly different meanings (and that may be what is confusing you).

In the first meaning, a "generator" is defined to be an element that generates the entire group. That is, when we talk about DH (and thus the group $\mathbb{Z}_p^*$), we say that $g$ generates the entire group means $g^k \bmod p$ can take on any value between 1 and $p-1$.

In the second meaning, we say that an element $g$ "generates" a subgroup. That is, when we consider all the possible values $g^k \bmod p$, those possible values also form a group (which may be $\mathbb{Z}_p^*$, and may be a strictly smaller group), and it makes sense to consider the Diffie-Hellman operation over this subgroup. In this case, we may call $g$ the "generator" (even if it doesn't generate the full group). Now, this doesn't denote anything special about $g$ (because all elements generate some subgroup by this meaning), instead we call $g$ the generator to denote that it's the element we have chosen to use.

As I pointed out in my answer to the cited question, using a "generator" for the entire group is often not wise; it often makes more sense to deliberately use an element that generates a prime-sized subgroup.

As to whether $g$ itself is prime or not, well, that's actually not very relevant. After all, $g$ is actually a member of $\mathbb{Z}_p^*$; whether it corresponds to a prime when it is mapped into $\mathbb{Z}$ using the obvious mapping is not that important.

-