Report Number: CS-TR-83-991
Institution: Stanford University, Department of Computer Science
Title: Parallel algorithms for arithmetics, irreducibility and factoring of GFq-polynomials
Author: Morgensteren, Moshe
Author: Shamir, Eli
Date: December 1983
Abstract: A new algorithm for testing irreducibility of polynomials over finite fields without gcd computations makes it possible to devise efficient parallel algorithms for polynomial factorization. We also study the probability that a random polynomial over a finite field has no factors of small degree.
http://i.stanford.edu/pub/cstr/reports/cs/tr/83/991/CS-TR-83-991.pdf