1
$\begingroup$

For a nonzero element $\alpha \in \mathbb F_{p^n}$ (the finite field of cardinality $p^n$) is there a simple criterion to tell whether $\alpha$ is a generator of the cyclic group $\mathbb F_{p^n}^\times$ by looking at the minimal polynomial of $\alpha$ over $\mathbb F_p$?

Here is what I know so far: Let $n\ge 1$ be an integer, $p$ be a prime and $\mathbb F_p = \mathbb Z/p\mathbb Z$ be the prime field of characteristic $p$. It is known that there is a unique (upto isomorphism) field $\mathbb F_{p^n}$ of cardinality $p^n$ which is the splitting field of $g (x) = x^{p^n} - x$.

If $f (x) \in \mathbb F_p [x]$ is monic irreducible of degree $n$ then $f (x)$ is separable and $\mathbb F_{p^n} \cong \mathbb F_p [t]/(f (t))$ is also the splitting field of $f (x)$. Further if $\alpha$ is any root of $f (x)$ in $\mathbb F_{p^n}$ then

  • $\mathbb F_{p^n} = \mathbb F_p (\alpha)$ (so $\alpha$ is a primitive element of the field extension $\mathbb F_{p^n}/\mathbb F_p$)
  • $m_{\alpha, \mathbb F_p} (x) = f (x)$ (the minimal polynomial of $\alpha$ over $\mathbb F_p$)
  • $f (x) = \prod\limits_{i = 0}^{n - 1} (x - \alpha^{p^i})$

Also, there are exactly

  • $M (n, p)/n$ distinct degree $n$ monic irreducible polynomials in $\mathbb F_p [x]$
  • $M (n, p) = \sum\limits_{d \mid n} p^{n/d} \mu (d)$ distinct primitive elements $\beta$ of $\mathbb F_{p^n}/\mathbb F_p$
  • $p^n - 1$ elements in the cyclic group $\mathbb F_{p^n}^\times$
  • $\phi (p^n - 1)$ generators of the cyclic group $\mathbb F_{p^n}^\times$

It is clear that each generator $\beta$ of the cyclic group $\mathbb F_{p^n}^\times$ is an element of degree $n$ over $\mathbb F_{p}$, i.e. $\deg m_{\beta, \mathbb F_p} (x) = n$, and hence is a primitive element of the field extension. It is also clear that all the other roots $\beta^{p^i}$ of the minimal polynomial $m_{\beta, \mathbb F_p} (x)$ are also generators of the cyclic group since $\gcd (p^i, p^n - 1) = 1$.

However in general the number of cyclic generators $\phi (p^n - 1)$ is much less than the number of primitive elements of the extension $M (n, p)$ (for example, for $n = 2$, $\phi (p^2 - 1)$ will be much less than $M (2, p) = p^2 - p$.

So now the question is:

  1. Characterise all the monic irreducible polynomials $f (x) \in \mathbb F_p [x]$ whose roots are cyclic generators of $\mathbb F_{p^n}^\times$.
  2. If $\beta$ is a cyclic generator of $\mathbb F_{p^n}^\times$ what are the indices $0 \le k < p^n$ for which the degree of $\beta^k$ over $\mathbb F_p$ is $n$ (or in general any $d \mid n$)?

P.S. I don't know any Galois theory, so if you use any of that, then I would appreciate if a reference is given.

$\endgroup$
  • $\begingroup$ See also math.stackexchange.com/questions/2373613/… $\endgroup$ – Chaitanya Tappu Nov 30 '18 at 2:33
  • $\begingroup$ For your information: in the context of finite fields an element is called primitive if and only if it is a generator of the multiplicative group of the extension field. See here for a more verbose explanation. Your tallies of polynomials are correct, but the terminology is off to this extent. $\endgroup$ – Jyrki Lahtonen Nov 30 '18 at 4:01
1
$\begingroup$

I only have a partial answer to your first question: Let $ p = 2 $ or $ p \equiv 1 \pmod 4 $. Then, if $ \alpha $ is a cyclic generator of $ \mathbb{F}_{p^n}^{\times} $ with minimal polynomial $ f(X) = X^n + a_{n-1}X^{n-1} + \cdots + a_0 \in \mathbb{F}_{p}[X] $, the last coefficient $ a_0 $ of $ f $ must be a generator of $ \mathbb{F}_{p}^{\times} $.

Proof: The case $ p=2 $ is trivial since the constant coefficient must be non-zero, so let $ p \equiv 1 \pmod 4 $. The roots of $ f $ are $ \alpha, \alpha^p, \cdots, \alpha^{p^{n-1}} $ and hence $ a_0 = (-1)^n \alpha^{\frac{p^n-1}{p-1}} $. Let $ d $ be the order of $ a_0 $. Then we get $$ 1 = a_0^d = (-1)^{nd} \alpha^{d \cdot \frac{p^n-1}{p-1}} \implies \alpha^{d \cdot \frac{p^n-1}{p-1}} = (-1)^{nd} \implies \alpha^{2d \cdot \frac{p^n-1}{p-1}} = 1 $$ It follows that $ p^n - 1 $ divides $ 2d \left( \frac{p^n-1}{p-1} \right) $. Then $ p-1 $ divides $ 2d $ but $ 2d \le 2(p-1) $ and so $ 2d = p-1 $ or $ 2d = 2(p-1) $. If the former case holds, then substituting $ d $ in the above gives $$ 1 = a_0^{\frac{p-1}{2}} = ((-1)^{n \cdot \frac{p-1}{2}}) (\alpha^{\frac{p^n-1}{2}}) = 1 \cdot (-1) = -1 $$ a contradiction. So the latter case holds and $ d = p-1 $ as desired.

This condition is not sufficient as the following example will show: Take $ p =5 $, $ n=2 $ and let $ \alpha $ be a root of the irreducible polynomial $ f(X)=X^2 + 2 \in \mathbb{F}_5[X] $. $ f $ has constant coefficient $ a_0=2 $ which is a generator of $ \mathbb{F}_5^{\times} $ but $ \alpha^2 = 3 \implies \alpha^8 = 3^4 = 1 $, so $ \alpha $ is not a cyclic generator of $ \mathbb{F}_{25}^{\times} $.

$\endgroup$

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.