<p>This problem is in BPP.</p>

<p>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$. </p>

<p>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$. </p>

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

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

<p>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.)</p>

<p>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. <a href="https://math.stackexchange.com/questions/1332522/is-finding-generators-of-finite-fields-hard">See this question on math.SE</a>. </p>

<p>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.)</p>

<p>Much of this is explained in <a href="https://en.wikipedia.org/wiki/Finite_field#Existence_and_uniqueness" rel="nofollow noreferrer">Wikipedia</a>. </p>

CC BY-SA 3.0
2016-10-23T22:51:54.277Z
2016-10-30T18:41:19.657Z
2017-04-13T12:19:19.363Z
Peter Shor 
<p>Suppose we have a finite field $\mathbb{F}_{p^n} = \frac{\mathbb{F}_{p}[x]}{&lt;f(x)&gt;}$. I want a deterministic polynomial algorithm to compute all subfields of this field. I think we can do something using linear algebra.</p>

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

CC BY-SA 3.0
2016-10-23T23:27:29.230Z
In what form do you want the algorithm to output the subfields?
Peter Shor 
CC BY-SA 3.0
2016-10-24T07:55:45.800Z
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...
Vanessa
<reference-request><finite-fields>
Constructing subfields of a finite field
xyz
# Constructing subfields of a finite field

(Asked by: username_0 on 2016-10-21)

Suppose we have a finite field $\mathbb{F}\_{p^n} = \frac{\mathbb{F}\_{p}[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.

**Tags:** reference-request, finite-fields
> **Comments:**
> **username_1**: In what form do you want the algorithm to output the subfields?  
> **username_2**: 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...  

---

## 1 answers

### Answer by username_1 on 2016-10-23. Score: 4

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](https://math.stackexchange.com/questions/1332522/is-finding-generators-of-finite-fields-hard).

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](https://en.wikipedia.org/wiki/Finite_field#Existence_and_uniqueness).


---

