New Algorithms for Generating Conway Polynomials over Finite Fields
Files
TR Number
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.