Parallel Algorithms for Arithmetics, Irreducibility and Factoring of GFq-Polynomials

摘要

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. The authors also study the probability that a random polynomial over a finite field has no factors of small degree.