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

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

-
Shoup's algorithm is randomized. As far as I am aware, deterministic polynomial-time construction of finite fields is an open problem. – Emil Jeřábek Feb 24 '14 at 9:26
@EmilJeřábek : I posted the wrong link. The updated link has Shoup's determinsitic algorithm. – user47368 Feb 24 '14 at 11:03
Oh I see. This algorithm is polynomial if the characteristic is constant. – Emil Jeřábek Feb 24 '14 at 11:59

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

-
Confirmed. This is lemma 1.1.28 on page 12. – user47368 Feb 24 '14 at 11:09