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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Zev Chonoles Apr 7 '15 at 4:04
  • $\begingroup$ Ah yes, you're right. I forgot there can be many generators. My mistake. I'll edit to reflect that. $\endgroup$ – Alfred Yerger Apr 7 '15 at 4:06
  • $\begingroup$ $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. $\endgroup$ – Al Jebr Apr 7 '15 at 6:59
  • 1
    $\begingroup$ @Pacman How is your comment relevant to the question? The question is about the multiplicative group of a finite field, not about $U(n)$. $\endgroup$ – Derek Holt Apr 7 '15 at 7:58

You are looking for a "primitive" element. In general these are fairly difficult to find.

For example: Finding primitive elements in finite fields of small characteristic


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.