From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: irredicible polynomials over GF(p)
Date: 6 Dec 1997 17:04:17 GMT

In article <66b1vo$nnu$1@sparcserver.lrz-muenchen.de>,
Helmut Richter <Helmut.Richter@lrz-muenchen.de> wrote:
>When I am given an integer n and a prime p and I want to have an
>arbitrary irreducible polynomial of degree n over GF(p): is there a
>better way than picking polynomials at random and see whether they are
>irreducible? In other words: can I exploit that my problem is only to
>find *any* irr. polynomial and is solved as soon as I have found the
>first one?

This may be of some use:

   Cantor, David G.(1-UCLA)
   On arithmetical algorithms over finite fields. (English)
   J. Combin. Theory Ser. A 50 (1989), no. 2, 285--300.
   
   This paper presents some efficient methods for calculating over ${\rm
   GF}(p\sp n)$ in the particular case when the exponent $n$ itself is a
   power of $p$, i.e., $n=p\sp k$. Usually, standard methods for
   calculating in finite fields ${\rm GF}(p\sp n)$ require the knowledge
   of an irreducible polynomial of degree $n$ over ${\rm GF}(p)$. Here an
   explicit basis, with multiplication table, is given for the fields
   ${\rm GF}(p\sp {p\sp k})$. At the same time, a simple recursive
   formula for finding irreducible polynomials which generate these
   fields is established.
   
   The author uses the same principles for giving an analogue of the fast
   Fourier transform from the additive point of view. The general fast
   Fourier transform is an efficient method for evaluating---or
   interpolating---a polynomial on the finite multiplicative subgroups of
   a field $F$. Here, in the particular case when the field $F$ is equal
   to ${\rm GF}(p\sp {p\sp k})$, one can work in a similar way on the
   finite additive subgroups of $F$. This yields new "fast" algorithms
   for polynomial computation.
             Reviewed by Brigitte Vallee
                 
   © Copyright American Mathematical Society 1990, 1997