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