# 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.
• @PeterTaylor, indeed -- and moreover in this case, we are working over $GF(2)$, and all polynomials over $GF(2)$ are monic. – D.W. Mar 8 '18 at 16:33
• Thinking about it, if you're working over $GF(2)$ and testing random polynomials you can easily improve the odds to $2/n$ by ensuring that you have an odd number of non-zero coefficients (i.e. don't select the constant coefficient randomly). – Peter Taylor Mar 8 '18 at 16:39