3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ In what form do you want the algorithm to output the subfields? $\endgroup$
    – Peter Shor
    Oct 23, 2016 at 23:27
  • 2
    $\begingroup$ 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... $\endgroup$
    – Vanessa
    Oct 24, 2016 at 7:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.