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



Constructing GF(2^n) in poly(n) time
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$. 


