Generator of the unit group

Question

I am required to find a generator of the unit group of $\mathbb{F}_{125}=\mathbb{F}_5[x]/(p(x))$, where $p(x)\in\mathbb{F}_5[x]$ is the irreducible polynomial $p(x)=x^3+x+1$. Does someone know how to find such an element easily and how to actually verify that a given candidate is a generator? Thank you very much in advance!

Answer 1

So, we are looking for a generator of $\mathbb{F}_{125}^*$, where $\mathbb{F}_{125}\simeq \mathbb{F}_5[x]/(x^3+x+1)$.

Since the group $\mathbb{F}_{125}^*$ has $124=2^2\cdot 31$ elements, $g\in\mathbb{F}_{125}^*$ is a generator iff: $$ g^{\frac{124}{2}}=g^{62}\neq 1,\qquad g^{\frac{124}{31}}=g^4\neq 1.$$ How to get a suitable candidate? Just take a random one.

Since $\varphi(124)=60$, almost half the elements of $\mathbb{F}_{125}^*$ are generators, so we don't even need to be extremely lucky. If we just test $g=x-1$, we have: $$ g^4 = -x,\qquad g^{62}=-1, $$ so $x-1$ is a generator for $\mathbb{F}_{125}^*$.

^{Footnote: If you have the Maxima CAS, this mechanism is yet implemented (by me :D) in the gf package.}