×

Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic. (English) Zbl 1120.13026

Summary: Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for
(1) computing the primary decomposition of ideals of polynomial rings defined over such fields and
(2) factoring arbitrary multivariate polynomials over such fields.
Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given.

MSC:

13P05 Polynomials, factorization in commutative rings
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13M10 Polynomials and finite commutative rings

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amrhein, B.; Gloor, O.; Kuechlin, W., Walking faster, (Calmet, J.; Limongelli, C., Design and Implementation of Symbolic Computation Systems. Design and Implementation of Symbolic Computation Systems, Springer LNCS, vol. 1128 (1996)), 150-161
[2] Becker, T.; Weispfenning, V., Gröbner Bases (1993), Springer Verlag: Springer Verlag New York
[3] Belabas, K., van Hoeij, M., Klüners, J., Steel, A., 2004. Factoring polynomials over global fields. Int. Math. Res. Not. (submitted for publication); Belabas, K., van Hoeij, M., Klüners, J., Steel, A., 2004. Factoring polynomials over global fields. Int. Math. Res. Not. (submitted for publication) · Zbl 1254.11116
[4] Bernardin, L.; Monagan, M., Efficient multivariate factorization over finite fields, (Proc. AAECC’97. Proc. AAECC’97, Springer LNCS, vol. 1255 (1997)), 15-28 · Zbl 1039.68934
[5] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system I: the user language, J. Symbolic Comput., 24, 3, 235-265 (1997), URL: · Zbl 0898.68039
[6] Collart, S.; Kalkbrener, M.; Mall, D., Converting bases with the Gröbner walk, J. Symbolic Comput., 24, 3-4, 465-469 (1997) · Zbl 0908.13020
[7] Davenport, J.H., Trager, B.M., 1981. Factorization over finitely generated fields. In: Proceedings of the 1981 Symposium on Symbolic and Algebraic Computation. Snowbird, Utah, pp. 200-205; Davenport, J.H., Trager, B.M., 1981. Factorization over finitely generated fields. In: Proceedings of the 1981 Symposium on Symbolic and Algebraic Computation. Snowbird, Utah, pp. 200-205 · Zbl 0481.68040
[8] Faugère, J.-C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computations of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput., 16, 329-344 (1993) · Zbl 0805.13007
[9] Geddes, K.; Czapor, S.; Labahn, G., Algorithms for Computer Algebra (1992), Kluwer: Kluwer Boston · Zbl 0805.68072
[10] Gianni, P.; Trager, B. M.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, J. Symbolic Comput., 6, 2-3, 149-167 (1988) · Zbl 0667.13008
[11] Kemper, G., The calculation of radical ideals in positive characteristic, J. Symbolic Comput., 34, 3, 229-238 (2002) · Zbl 1010.13001
[12] Knuth, D. E., The Art of Computer Programming, vol. 2 (1998), Addison Wesley: Addison Wesley Reading, MA · Zbl 0191.17903
[13] Steel, A., 2004. Conquering inseparability (examples web page).http://magma.maths.usyd.edu.au/users/allan/insep; Steel, A., 2004. Conquering inseparability (examples web page).http://magma.maths.usyd.edu.au/users/allan/insep
[14] Trager, B. M., Algebraic factoring and rational function integration, (Jenks, R. D., Proc. SYMSAC’76 (1976), ACM Press), 196-208
[15] van Hoeij, M., Factoring polynomials and the knapsack problem, J. Number Theory, 95, 2, 167-189 (2002) · Zbl 1081.11080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.