Minimal polynomial of a finite field Let $p,n\in\mathbb{N}$ with $p$ prime and $q=p^n$. Let $\mathbb{F}_q$ be the finite field with $q$ elements (unique up to $\cong$), i.e. the $q$-th Galois field. According to this, the extension $\mathbb{Z}_p\leq\mathbb{F}_q$ is simple, so we must have $$\mathbb{F}_q\cong\mathbb{Z}_p[x]/(f)$$
for some irreducible polynomial $f\in\mathbb{Z}_p[x]$. What is the formula for this $f$?
 A: $f$ need not be unique. Take $\mathbf{Z}_5$ with $f=x^2-2,g=x^2-3$. Both give fields with $25$ elements.
A: As far as I know, there is no "formula" to produce an irreducible polynomial of arbitrary degree over an arbitrary finite field. There are, however, algorithms, which are basically just very complicated formulas. :)
Many computer algebra systems have a function for this. For example in Pari this function is called ffinit, and the documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
A: As mentioned above, $f$ need not be unique. You can take $f$ to be any irreducible (over $\mathbb{F}_p$) polynomial of degree $n$, and for any root $\alpha$ of $f$, $\mathbb{F}_q \cong \mathbb{F}_p(\alpha) \cong \mathbb{F}_p[x]/(f)$
Edit: If you want explicit irreducible polynomials of a given degree $n$ over $\mathbb{F}_p$, you can recursively use the fact that $x^{p^n} - x$ is the product of all irreducible polynomials of degree $d$ over $\mathbb{F}_p$, where $d$ runs over divisors of $n$. E.g. over $\mathbb{F}_2$, $x^{p^2} - x = x^4 - x = x(x+1)(x^2+x+1)$, so for $p = 2, n = 2$, there happens to be a unique irreducible polynomial defining $\mathbb{F}_4$ (but from this one can easily see that in general, there will be many such irreducibles).
