Efficiently generating a prime polynomial of a given degree
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.