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