Is it possible to find out a general formula for one polynomial of degree $n$ that is irreducible over $\mathbb F_p$ ?
irreducible polynomials of deg n in $\mathbb F_p$
-
1It looks like there is some useful information in http://cdn.intechopen.com/pdfs/10965/InTech-Systematic_generation_of_an_irreducible_polynomial_of_an_arbitrary_degree_m_over_fp_such_that_p_m.pdf – 2012-11-26
2 Answers
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.
-
0Sorry, what is $Q$ supposed to be? – 2012-11-26
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.