Decomposing polynomial sets into simple sets over finite fields: The zero-dimensional case

This paper presents algorithms for decomposing any zero-dimensional polynomial set into simple sets over an arbitrary finite field, with an associated ideal or zero decomposition. As a key ingredient of these algorithms, we generalize the squarefree decomposition approach for univariate polynomials over a finite field to that over the field product determined by a simple set. As a subprocedure of the generalized squarefree decomposition approach, a method is proposed to extract the pth root of any element in the field product. Experiments with a preliminary implementation show the effectiveness of our algorithms. (C) 2010 Elsevier Ltd. All rights reserved.