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.
In a related question on MathOverflow, Igor Rivin provides a link to a 2009 pre-print of a paper of Couveignes and Lercier, Fast construction of irreducible polynomials over finite fields, which uses elliptic curves to provide a probabilistic quasi-linear algorithm. The paper was published in Israel Journal of Mathematics (2013) vol. 194, pp 77–105, DOI https://doi.org/10.1007/s11856-012-0070-8