Probabilistic Algorithms in Finite Fields

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 throng Zp is not feasible, our algorithms are of lower order in the degrees of the polynomial and fields in question, than previously published algorithms.