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.