Probabilistic Algorithms in Finite Fields

Abstract

We present probabilistic algorithms for the problems of finding an irreducible polynomial of degree n over a finite field, finding roots of a polynomial, and factoring a polynomial into its irreducible factors over a finite field. All of these problems are of importance in algebraic coding theory, algebraic symbol manipulation, and number theory. These algorithms have a very transparent, easy to program structure. For finite fields of large characteristic p, so that exhaustive search through ${\text{Z}}_p $, is not feasible, our algorithms are of lower order in the degrees of the polynomial and fields in question, than previously published algorithms.