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 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