Factoring polynomials over finite fields: Asymptotic complexity vs. reality
Victor Shoup · 1993
Several algorithms for factoring polynomials over finite fields are compared from the point of view of asymptotic complexity, and from a more realistic point of view: how well actual implementations perform on "moderately" sized inputs. 1 Introduction The purpose of this paper is to examine several algorithms for factoring polynomials over finite fields, from both the point of view of asymptotic complexity, and from a more realistic point of view: how well actual implementations perform on "moderately" sized inputs. We restrict our attention to factoring in Z p [x], where p is prime. The algorithms we consider are the algorithms of Berlekamp [B], Cantor & Zassenhaus [CZ], and von zur Gathen & Shoup [GS]. 2 Asymptotic Complexity Let n be the degree of the polynomial f 2 Z p [x] to be factored. It is natural to measure the running times of factorization algorithms in terms of the number of operations in Z p (additions, subtractions, multiplications, divisions, and zero-tests). All of t...