# Generating elements of large group of units of a field.

Suppose $F$ is a large but finite field, and $F^\text{x}$ is the group of non-zero elements of the field. It is known that this group is always cyclic, and we could ask a natural question "what are the generators of the group?" This is easy to determine for small groups, but quite difficult for large groups it seems. Consider two examples.

First consider $F=\mathbb Z /(3)[x]/(x^2+1)$. $F^\text {x}$ has exactly 8 elements in it. To find the generator, we can first find the element of order 2 by solving the equations $ax+b = 1,$ for $a,b \in \{0,1,2\}.$ This calculation yields that the element of order 2 is 2 (which is also evident from the fact that $x^2 = 2$ in this group). We can repeat this process twice more since $8=2^3$ solving similar equations until we find a generator, namely $(x+1)$. A quick check shows that $(x+1)^8=1,$ so we're done.

However, consider this larger field: $F= \mathbb Z/(3)[x]/(x^4+x+2)$. This is a finite field with 81 elements, so that $F^\text {x}$ has 80 elements. This approach is not so feasible, as by the second calculation, the sheer number of possibilities to check is staggering. And this too is comparatively tame, as all the coefficients are reduced mod 3.

So to summarize, the question is how can I determine a generator of an arbitrary cyclic group of order $p^k - 1,$ where $p$ is a large prime, and $k$ a large integer?

• You're asking for "the" generator, but in fact a cyclic group of order $n$ has $\varphi(n)$ generators, where $\varphi$ is Euler's phi function. – Zev Chonoles Apr 7 '15 at 4:04
• Ah yes, you're right. I forgot there can be many generators. My mistake. I'll edit to reflect that. – Alfred Yerger Apr 7 '15 at 4:06
• $U(\mathbb Z/n\mathbb Z)$ is not always cyclic. For example: $U(\mathbb Z/15\mathbb Z)$ is not cyclic. There are no primitive roots. – Al Jebr Apr 7 '15 at 6:59
• @Pacman How is your comment relevant to the question? The question is about the multiplicative group of a finite field, not about $U(n)$. – Derek Holt Apr 7 '15 at 7:58