# irreducible polynomials of deg n in $\mathbb F_p$

Is it possible to find out a general formula for one polynomial of degree $n$ that is irreducible over $\mathbb F_p$ ?

-
What’s the quantification on the $n$ and the $p$? – Lubin Nov 25 '12 at 18:36
It looks like there is some useful information in cdn.intechopen.com/pdfs/10965/… – Gerry Myerson Nov 26 '12 at 0:13

Markus Nijmeijer and Mike Staring, A formula that produces all, and nothing but, irreducible polynomials in ${\bf Z}_p[x]$, Mathematics Magazine Vol. 61, No. 1, Feb., 1988, pages 41-44, says

Let $p$ be a prime and let $A_p$ denote the collection of all polynomials of degree $2$ or more in ${\bf Z}_p[x]$, then the formula $$F(P(x))=[Q^2(x)\bmod{P(x)}]P(x)+[(1-Q^2(x))\bmod{P(x)}](x^p-x-1),$$ $P(x)$ in $A_p$, generates all irreducible polynomials in ${\bf Z}_p[x]$.

I don't think it's meant to be a practical method for generating irreducible polynomials of a given degree.

EDIT: $Q(x)$ denotes the product of all the nonzero elements of the ring ${\bf Z}_p[x]/(P(x))$. The result rests on a polynomial analogue of Wilson's Theorem.

-
Sorry, what is $Q$ supposed to be? – Martin Brandenburg Nov 26 '12 at 0:31

Partial answer for $n=p$: the polynomial $x^p - x - j$ is irreducible over $Z/p[x]$ for $1 \leq j \leq p-1$ (this was a homework problem when I took Galois theory). In general, of course, one can count the number of irreducible polynomials of any fixed degree (see Lidl and Niederreiter) but finding them is quite hard.

-