Efficiently generating a prime polynomial of a given degree

I'm playing around with finite field arithmetic and implementing it in a little library. I'd like to be able to handle arbitrary finite fields given their size and characteristic. I don't want to write down a prime polynomial for every given possible finite field though. How can I generate a prime polynomial of a given degree for use in multiplication? To be clear I don't care which polynomial I get, and I don't want all of them. I just want any old one of a given degree. If this is an open research question what if we only try to solve it for $GF(2^n)$?

It suffices to construct an irreducible polynomial of degree $n$ over $GF(2)$ (as this immediately induces an explicit construction for $GF(2^n)$). So, how do you generate an irreducible polynomial?

One approach is to repeatedly choose a random polynomial of degree $n$, then test whether it is irreducible. You can test for irreducibility by factoring the polynomial over $GF(2)$. There are standard algorithms for polynomial factorization; they run in polynomial time. Moreover, about a $1/n$ fraction of all polynomials are irreducible (see here). It follows that on average about $n$ iterations will suffice, and since each iteration can be done in polynomial time, the whole thing runs in (randomized) polynomial time.

StackExchange Computer Science Q#89044, answer score: 2