It takes some group theory and Fermat's little theorem to explain the details (I have posted the group theory details in the appropriate presentation, but did not go over any proofs in class. So you will have to believe the facts, and are not expected

to know how to prove them).

If p is a prime, then the integers in the set $\{1,2,\ldots,p-1\}$ form a group with respect to the operation of multiplication

modulo p. Furthermore, this group is **cyclic**: There is an element, g, such that the various powers of g, namely $\{g,g^2,\ldots,g^{p-1}\}$ are all different and thus expand all of $\{1,2,\ldots,p-1\}$ (all operations are modulo p).

Such g is called a **multiplicative generator** of the grouo.

If $h\in \{1,2,\ldots,p-1\}$ is not a multiplicative generator, then the various powers of h, namely $\{h,h^2,\ldots,h^{p-1}\}$ form a proper subgroup of $\{1,2,\ldots,p-1\}$. By Lagrange theorem, the number of elements in such subgroup must divide p-1, which is the number of elements in the whole group. Denote this number by m, then m is a divisor of p-1, and m<p-1. By Fermat's little theorem, this implies $h^m=1 \pmod p$.

So if for some g, $g^m\neq 1 \pmod p$ for all proper divisors m of p-1, such g must be a multiplicative generator.

In Diffie Hellman key exchange we use such multiplicative generator as part of the information known by everyone.

Raising g to some power is easy. Doing the inverse (taking "discrete logs") is **believed** to be hard.