New Algorithms for Generating Conway Polynomials over Finite Fields

Abstract

Arithmetic in a finite field of prime characteristic p normally employs an irreducible polynomial in Z_p[X]. A particular class of irreducible polynomials, generally known as Conway polynomials, provides a means for representing several finite fields of characteristic p in a compatible manner. Conway polynomials are used in computational algebra systems such as GAP and Magma to represent finite fields. The generation of the Conway polynomials for a particular finite field has previously been done by an often expensive brute force search. As a consequence, only a few Conway polynomials have been generated. We present two algorithms for generating Conway polynomials that avoid the brute force search. We have implemented one of these algorithms in Magma and present numerous new Conway polynomials that implementation generated.