0
$\begingroup$

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

  • 1
    It 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.pdf2012-11-26

2 Answers 2

2

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.

  • 0
    Sorry, what is $Q$ supposed to be?2012-11-26
0

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.