ON SQUARE-FREE FACTORIZATION OF MULTIVARIATE POLYNOMIALS OVER A FINITE-FIELD

In this paper we present a new deterministic algorithm for computing t he square-free decomposition of multivariate polynomials with coeffici ents from a finite field. Our algorithm is based on Yun's square-fee f actorization algorithm for characteristic 0. The new algorithm is more efficient than existing, deterministic algorithms based on Musser's s quare-free algorithm. We will show that the modular approach presented by Yun has no significant performance advantage over our algorithm. T he new algorithm is also simpler to implement and it can rely on any e xisting GCD algorithm without having to worry about choosing ''good'' evaluation points. To demonstrate this, we present some timings using implementations in Maple (Char et al., 1991), where the new algorithm is used for Release 4 onwards, and Axiom (Jenks and Sutor, 1992) which is the only system known to the author to use an implementation of Yu n's modular algorithm mentioned above.