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?)

  • 1. T. Becker and V. Weispfenning, Gröbner Bases, A Computational Approach to Commutative Algebra, GTM 141, Springer, New York, 1993. MR 1213453 (95e:13018)
  • 2. E.R. Berlekamp, ``Factoring polynomials over finite fields'', Bell System Technical J., 46(1967), 1853-1859. MR 0219231 (36:2314)
  • 3. E.R. Berlekamp, ``Factoring polynomials over large finite fields'', Mathematics of Computation 24 (1970), 713-735. MR 0276200 (43:1948)
  • 4. D. COX, J. LITTLE AND D. O'SHEA, Using algebraic geometry, Graduate Texts in Mathematics, 185, Springer-Verlag, New York, 1998. MR 1639811 (99h:13033)
  • 5. W. DECKER, G.-M. GREUEL AND G. PFISTER, ``Primary decomposition: algorithms and comparisons'', Algorithmic algebra and number theory (Heidelberg, 1997), 187-220, Springer, Berlin, 1999. MR 1672046 (99m:13049)
  • 6. D. EISENBUD, Commutative algebra, With a view toward algebraic geometry, Graduate Texts in Mathematics, 150, Springer-Verlag, New York, 1995. xvi+785 pp. MR 1322960 (97a:13001)
  • 7. D. EISENBUD, C. HUNEKE AND W. VASCONCELOS, ``Direct methods for primary decomposition'', Invent. Math. 110 (1992), no. 2, 207-235. MR 1185582 (93j:13032)
  • 8. J. Faugere, P. Gianni, D. Lazard and T. Mora, ``Efficient computation of zero-dimensional Gröbner bases by change of ordering'', J. Symbolic Comput. 16 (1993), 329-344. MR 1263871 (94k:68095)
  • 9. S. GAO, ``Factoring multivariate polynomials via partial differential equations'', Mathematics of Computation 72 (2003), 801-822. MR 1954969 (2003m:12014)
  • 10. S. Gao, Y. Guan and R. Heindl, ``Factoring bivariate polynomials via Niederreiter's differential equation'', in preparation.
  • 11. S. Gao, V. M. Rodrigues and J. Stroomer, ``Gröbner basis structure of finite sets of points'', preprint 2003.
  • 12. H.-G. GR¨ABE, ``Minimal primary decomposition and factorized Gröbner bases'', Appl. Algebra Engrg. Comm. Comput. 8 (1997), no. 4, 265-278. MR 1464788 (98k:13031)
  • 13. P. Gianni, B. M. Trager and G. Zacharias, ``Gröbner bases and primary decomposition of polynomial ideals'', J. Symbolic Comput., 6 (2-3), 1988, 149-167. MR 988410 (90f:68091)
  • 14. G.-M. GREUEL AND G. PFISTER, A SINGULAR Introduction to Commutative Algebra, Springer-Verlag 2002, xvii + 588 pp. MR 1930604 (2003k:13001)
  • 15. M. VAN HOEIJ, ``Factoring polynomials and the knapsack problem'', Journal of Number Theory 95 (2002), 167-189. MR 1924096 (2003f:13029)
  • 16. G. LECERF ``Sharp precision in Hensel lifting for bivariate polynomial factorization'', Mathematics of Computation 75 (2006), 921-933. MR 2197000 (2007g:12008)
  • 17. C. Monico, ``Computing the primary decomposition of zero-dimensional ideals'', J. Symbolic Comput. 34 (2002), 451-459. MR 1937469 (2003i:13036)
  • 18. H. NIEDERREITER, ``A new efficient factorization algorithm for polynomials over small finite fields'', Appl. Alg. Eng. Comm. Comp. 4 (1993), 81-87. MR 1223850 (94h:11112)
  • 19. H. NIEDERREITER, ``Factoring polynomials over finite fields using differential equations and normal bases'', Math. Comp. 62 (1994), 819-830. MR 1216262 (94g:11113)
  • 20. J.F. RITT, Differential algebra. Dover Publications, Inc., New York, 1966 viii+184 pp. MR 0201431 (34:1315)
  • 21. A. SAUSSE, ``A new approach to primary decomposition'', Computational Algebra and Number Theory (Milwaukee, WI, 1996). J. Symbolic Comput. 31 (2001), no. 1-2, 243-257. MR 1806219 (2002k:13038)
  • 22. A. SEIDENBERG, ``On the Lasker-Noether decomposition theorem'', American J. Math. 106 (1984), 611-638. MR 745143 (86b:03078)
  • 23. T. SHIMOYAMA AND K. YOKOYAMA, ``Localization and primary decomposition of polynomial ideals'', J. Symbolic Comput. 22 (1996), no. 3, 247-277. MR 1427183 (98a:13038)
  • 24. A.K. STEEL, ``Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic'', J. Symbolic Comput. 40 (2005), 1053-1075. MR 2167699 (2006f:13023)
  • 25. W.V. VASCONCELOS, Computational methods in commutative algebra and algebraic geometry, With chapters by David Eisenbud, Daniel R. Grayson, Jürgen Herzog and Michael Stillman. Algorithms and Computation in Mathematics, 2, Springer-Verlag, Berlin, 1998. xii+394 pp. MR 1484973 (99c:13048)
  • 26. D. WAN, ``Computing zeta functions over finite fields'', Contemporary Mathematics, 225 (1999), 131-141. MR 1650604 (99j:11073)
  • 27. D. WANG, ``Decomposing algebraic varieties'', Automated deduction in geometry (Beijing, 1998), 180-206, Lecture Notes in Comput. Sci., 1669, Springer, Berlin, 1999. MR 1775951 (2001f:68144)
  • 28. WEN JUN WU, ``Basic principles of mechanical theorem proving in elementary geometries'', J. Systems Sci. Math. Sci. 4 (1984), no. 3, 207-235. MR 795000 (87g:03017)
  • 29. WEN TSUN WU, Mechanical theorem proving in geometries. Basic principles. Translated from the 1984 Chinese original by Xiao Fan Jin and Dong Ming Wang. Texts and Monographs in Symbolic Computation. Springer-Verlag, Vienna, 1994. xiv+288 pp. MR 1284925 (96a:68110)

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