# Steps to determine the single element generators for a multiplicative group

As student I've been asked the following question:

Consider the specific prime $$p=17$$. Determine the single element generators (by hand or by Java program) of $$F^*_{17}$$. Recall $$F^*_{17}$$ is the multiplicative group of size $$16 = 17−1$$ formed by removing $$0$$ from the field $$F^*_{17}$$.

Can anyone explain what the steps are in order to attempt the question?

• Welcome to Cryptography. For homework questions we provide hints. A generator $g$ of a group $G$, where the $F^*_{17}$ is a multiplicative cyclic group, is an element such that when you multiply $g$ itself, again and again, you will get all the elements of the group. Eventually, it will be 1. Now can you think methods? Also, see Little Fermat theorem, – kelalaka Mar 14 at 12:40

The problem with picking a random group element as a generator is that it might actually be a generator of a smaller subgroup. By Euler's theorem, every element raised to the power of the group order, $$n$$, is $$1$$. That is, if $$x$$ is an element of a subgroup of order $$k$$, then
$$x^n = x^{km} = (x^k)^m = 1^m = 1.$$
So it is not sufficient to check that an element raised to the $$n$$th power is $$1$$, since this is satisfied by all group elements.
But it is not necessary to check every exponent $$[1,n]$$ to see if it generates a subgroup because, by Lagrange's theorem, there can be at most one subgroup for every divisor of $$n$$. So it suffices to check divisors of $$n$$ as exponents to see if they generate the group identity.