Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|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 at 9:26
    
@EmilJeřábek : I posted the wrong link. The updated link has Shoup's determinsitic algorithm. –  user47368 Feb 24 at 11:03
    
Oh I see. This algorithm is polynomial if the characteristic is constant. –  Emil Jeřábek Feb 24 at 11:59
add comment

1 Answer

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|improve this answer
    
Confirmed. This is lemma 1.1.28 on page 12. –  user47368 Feb 24 at 11:09
add comment

Your Answer

 
discard

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.