How to find all of generators in a finite fields

Question

How can I find all generators of a finite field?

For example in GF(2^3) and X^3 + x^2 + 1 as primitive polynomial.

I don`t want all of solutions. I need some hint and help to solve this problem.

Thanks a lot.

Ya Ali.

Answer 1

the multiplicative group of $GF_{2^3}$ has prime order, so that tells you how many generators it has. also note what is the only subfield of $GF_{2^3}$ (a generator cannot lie in a subfield). and finally note that there are precisely two irreducible polynomials of degree $3$ over $GF(2)$. try computing the first seven powers of $\alpha$ where $1+\alpha^2+\alpha^3=0$, expressing each as a linear combination of $1, \alpha, \alpha^2$ with coefficients in $GF(2)$

Answer 2

For future readers, I will add the following to try to clear up the other comments and answers.

Working in the finite field $GF(p^n)=GF(p)[x]/g(x)$ (with $g(x)$ of degree $n$ and irreducible in $GF(p)[x]$), the multiplicative subgroup comprises $p^n-1$ elements. The polynomial $\alpha(x)$ is a generator for that group if and only if its order is $p^n-1$, which means its powers $\{\alpha(x)^k\mid k=0,1\,... p^n-2\}$ generate the entire multiplicative subgroup in the finite field (all elements apart from $0$).

As was pointed out, if $\alpha(x)$ is a generator, then so is $\alpha(x)^i$ where $i$ is given by $\gcd(i,p^n-1)=1$, which means $i$ and the order of the multiplicative subgroup are coprime (they don't share divisors greater than $1$). To see why this condition, consider what it means if this were not the case: let the common divisor be $d>1$, then $p^n-1=ad$ and $i=bd$. Taking the $k$th power of such a generator, $(\alpha(x)^i)^k=(\alpha(x)^b)^{dk}$, we see that $k$ can only take on $a$ values instead of $p^n-1$ before $(\alpha(x)^i)^k=(\alpha(x)^b)^{da}=1$, so $\alpha(x)^i$ has too few powers to generate the field. On the flip side, if $\gcd(i,p^n-1)=1$, then it must take $k$ exactly $p^n -1 $ values to get to $p^n-1$, which means the powers of $\alpha(x)^i$ generate the field in that case.

The number of $i\in\mathbb{N}$ and $i\leq p^n-1$ that satisfy $\gcd(i,p^n-1)=1$ is given exactly by $\phi(p^n-1)$.

The OP also commented that he wanted to find generating polynomials other than the simple monomial $\alpha^i$, like say a polynomial $\alpha^i+\alpha^{i-1}+\dots$. This is the danger in using $\alpha$ instead of $\alpha(x)$: my guess is that the OP actually meant that they wanted $\alpha(x)^i$ of a form other than the monomial $x^i$, but $\alpha(x)$ as used in the given answers can be any polynomial, not just $x^i$.

For example, in $GF(2^4)=GF(2)[x]/(x^4+x+1)$, we have the generator $\alpha(x) = x^3 + x + 1$, but also the generator $x$. Indeed, the two are related, e.g. by $x^7 = x^3 + x + 1 \mod(x^4+x+1)$. It is not surprising that the 7th power of generator $x$ is also a generator, since $\gcd(7,2^4-1)=1$.

Answer 3

Once you find a generator g of a finite cyclic group of order k, the set of generators is just {g^i | gcd(i,k) = 1}. So there are phi(k) of them, where phi is the Euler totient function. And note that the multiplicative group of a finite field GF(p^n) is always cyclic of order p^n-1.