Constructing GF(2^n) in poly(n) time

Question

I need to, on input $n$, deterministically, in poly(n) time, construct $GF(2^n)$.

There is a very simple randomized algorithm (pick a random polynomial, check if it's irreducible; if not, repeat).

Shoup http://www.shoup.net/papers/detirred.pdf has a deterministic algorithm.

I'm wondering, for the case of $GF(2^n)$, which is used in many error correcting codes, if there's a simpler derandomization.

Thanks!

context:

a non-trivial number of results in derandomization ends up using small bias distributions

in http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias.ps section 3.1, both constructions appear to require not only the existence, but also the ability to deterministically construct the finite field

errata

the original paper I linked was randomized; I now updated it to have correct link

Answer 1

I think there is a special construction that works for certain values of $n$.

Assume that $n = 2\cdot 3^\ell$ for some $\ell\in\mathbb{N}$. Then, we know the following (see Chapter 1 of the book by van Lint on Coding Theory for the proof):

The polynomial $p(x) = x^{n} + x^{n/2} + 1$ is irreducible in $\mathbb{F}_2[x]$.

One can use this polynomial to construct field extensions for these specific values of $n$.