Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Primary decomposition of zero-dimensional ideals over finite fields

Authors: Shuhong Gao, Daqing Wan and Mingsheng Wang
Journal: Math. Comp. 78 (2009), 509-521
MSC (2000): Primary 13P10, 68W30; Secondary 11Y16, 12Y05, 13P05.
Published electronically: May 1, 2008
MathSciNet review: 2448718
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A new algorithm is presented for computing primary decomposition of zero-dimensional ideals over finite fields. Like Berlekamp's algorithm for univariate polynomials, the new method is based on the invariant subspace of the Frobenius map acting on the quotient algebra. The dimension of the invariant subspace equals the number of primary components, and a basis of the invariant subspace yields a complete decomposition. Unlike previous approaches for decomposing multivariate polynomial systems, the new method does not need primality testing nor any generic projection, instead it reduces the general decomposition problem directly to root finding of univariate polynomials over the ground field. Also, it is shown how Gröbner basis structure can be used to get partial primary decomposition without any root finding.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 13P10, 68W30, 11Y16, 12Y05, 13P05.

Retrieve articles in all journals with MSC (2000): 13P10, 68W30, 11Y16, 12Y05, 13P05.

Additional Information

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975

Daqing Wan
Affiliation: Department of Mathematics, University of California, Irvine, California 92697-3875

Mingsheng Wang
Affiliation: Information Security laboratory, Institute of Software, Chinese Academy of Sciences, Box 8718, Beijing 100080, People’s Republic of China
Email: mingsheng\

Keywords: Primary decomposition, primary ideals, quasi-primary ideals, Groebner bases, Frobenius map.
Received by editor(s): December 1, 2006
Received by editor(s) in revised form: October 29, 2007
Published electronically: May 1, 2008
Additional Notes: The work was done while the authors were visiting IMA at University of Minnesota in Fall 2006. Gao and Wan were supported in part by National Science Foundation (NSF), and Wang was partially supported by 973 Projects (2004CB318004) and NSFC (60573041).
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society