Constructing subfields of a finite field

Suppose we have a finite field $\mathbb{F}_{p^n} = \frac{\mathbb{F}_{p}[x]}{<f(x)>}$. I want a deterministic polynomial algorithm to compute all subfields of this field. I think we can do something using linear algebra.

Can someone suggest a reference of this problem? I am unable to find it in standard texts.

• In what form do you want the algorithm to output the subfields? Oct 23, 2016 at 23:27
• The subfields of $\mathbb{F}_{p^n}$ are just all $\mathbb{F}_{p^m}$ for $m$ that divides $n$. $\mathbb{F}_{p^m}$ is uniquely embedded in $\mathbb{F}_{p^n}$ as the roots of the polynomial $x^{p^m} - x$. But perhaps you're looking for a particular representation... Oct 24, 2016 at 7:55

This problem is in BPP.

All finite fields of order $p^n$ are identical, and there is a generator element $g$ whose multiplicative order is $p^n-1$, so every non-zero field element is expressible as $g^r$ for some $r$.

Now, there is a subfield of order $p^j$ iff $j$ divides $n$, and this subfield has a generator element $h$ whose multiplicative order is $p^j-1$.

This means that we can take $h = g^{(p^n-1)/(p^j-1)}$.

What this means, in effect, is that once we have an algorithm for finding a generator of the finite field, everything else is straightforward.

The easy way to find a generator is to pick a field element at random, and test whether it is a generator. The expected number of elements you need to test is indeed polynomial. Doing this test efficiently might require knowing the prime factors of $n$. (But if you can write down all the coefficients of $f(x)$ without using sparse polynomial notation, then $n$ is small and this is easy.)

But you asked for a deterministic algorithm and not a randomized one. A quick search shows that there is no known efficient deterministic algorithm for finding a generator. See this question on math.SE.

So the question is: can you find a deterministic algorithm for finding the subfields which doesn't actually compute a generator for the subfields? (Because that's probably as hard as finding a generator for the field itself, and so is an open problem.)

Much of this is explained in Wikipedia.