MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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



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

in section 3.1, both constructions appear to require not only the existence, but also the ability to deterministically construct the finite field


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

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
Confirmed. This is lemma 1.1.28 on page 12. – user47368 Feb 24 '14 at 11:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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