×

Factoring polynomials over local fields. (English) Zbl 1085.12500

Summary: We describe an efficient new algorithm for factoring a polynomial \(\Phi (x)\) over a field \(k\) that is complete with respect to a discrete prime divisor. For every irreducible factor \(\phi (x)\) of \(\Phi (x)\) this algorithm returns an integral basis for \(k[ x ] / \phi (x)k[ x ]\) over \(k\).

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
11S05 Polynomials
13P05 Polynomials, factorization in commutative rings
68W30 Symbolic computation and algebraic computation

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berlekamp, E., Factoring polynomials over large finite fields, Math. Comput., 24, 713-735 (1970) · Zbl 0247.12014
[2] Cannon, J., The Magma Computational Algebra System (2000 Available online at http://www.maths.usyd.edu.au:8000/u/magma/index.html), University of Sydney: University of Sydney Australia
[3] Cantor, D. G.; Gordon, D., Factoring polynomials over \(p\) -adic fields, Proceedings of ANTS IV (2000), Springer-Verlag: Springer-Verlag Berlin · Zbl 1006.11066
[4] Cantor, D. G.; Zassenhaus, H., A new algorithm for factoring polynomials over finite fields, Math. Comput., 36, 587-592 (1981) · Zbl 0493.12024
[5] Chistov, A. L., Efficient factoring polynomials over local fields and its applications, Proceedings of ICM 1990 (1991), Springer-Verlag: Springer-Verlag Berlin, p. 1509-1519 · Zbl 0761.11045
[6] Cohen, H., Advanced Topics in Computational Number Theory (1999), Springer-Verlag: Springer-Verlag New York
[7] Cohen, H., A Course in Computational Number Theory (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0786.11071
[8] Fieker, C.; Friedrichs, C., On reconstruction of algebraic numbers, Proceedings of ANTS IV (2000), Springer-Verlag: Springer-Verlag Berlin · Zbl 0990.11084
[9] D. Ford, 1978; D. Ford, 1978
[10] Ford, D., The construction of maximal orders over a Dedekind domain, J. Symb. Comput., 4, 69-75 (1987) · Zbl 0632.13003
[11] Ford, D.; Letard, P., Implementing the Round Four maximal order algorithm, J. Théor. Nombres de Bordeaux, 6, 39-80 Available online at http://almira.math.u-bordeaux.fr:80/jtnb/1994-1/jtnb6-1.html (1994) · Zbl 0817.11064
[12] D. Ford, S. Pauli, X.-F. Roblot, 2000 Available online at http://www-cicma.concordia.ca/faculty/cicma/CP00.html, Concordia Laval McGill, Montreal, Canada; D. Ford, S. Pauli, X.-F. Roblot, 2000 Available online at http://www-cicma.concordia.ca/faculty/cicma/CP00.html, Concordia Laval McGill, Montreal, Canada
[13] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press New York · Zbl 0936.11069
[14] Hafner, J.; McCurley, K., Asymptotically fast triangulization of matrices over rings, SIAM J. Comput., 20, 1068-1083 (1991) · Zbl 0738.68050
[15] Kaltofen, E.; Shoup, V., Subquadratic-time factoring of polynomials over finite fields, Math. Comput., 67, 1179-1197 (1998) · Zbl 0902.11053
[16] J. Montes, 1999; J. Montes, 1999
[17] Ore, Ö., Newtonsche Polygone in der Theorie der algebraischen Körper, Math. Ann, 99, 84-117 (1928)
[18] Pohst, M. E., Factoring polynomials over global fields, J. Symb. Comput. (1999 submitted.)
[19] Pohst, M. E.; Zassenhaus, H., Algorithmic Algebraic Number Theory (1989), Cambridge University Press: Cambridge University Press Cambridge, U.K · Zbl 0685.12001
[20] Roblot, X.-F, Factorization algorithms over number fields, J. Symb. Comput. (2000 submitted.)
[21] Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007
[22] Trager, B. M., Algebraic factoring and rational function integration, Proceedings of the Symposium on Symbolic and Algebraic Computation (1976), ACM Press: ACM Press New York, p. 219-226 · Zbl 0498.12005
[23] Weiss, E., Algebraic Number Theory (1963), McGraw-Hill · Zbl 0115.03601
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.