I'm looking for constructive ways to obtain finite fields, for any given size $q=p^n$. For example, I know it suffices to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (and then obtain the field as its quotient ring), but how can such polynomial be efficiently found?
Also, I know there are more ways to represent elements of finite fields – are they easier to use than the irreducible polynomial method? What is done in practice in computational mathematical libraries?
Best Answer
In practice, one guesses an $n$'th degree polynomial and tests it for irreducibility. As a random polynomial has about a $1/n$ probability of being irreducible, this does not take too long. For variations and improvements on this idea see this paper by Shoup (author of the NTL library, which you may also want to look at.)