Abstract
We present an algorithm for factoring polynomials over local fields, in which the Montes algorithm is combined with elements from Zassenhaus Round Four algorithm. This algorithm avoids the computation of characteristic polynomials and the resulting precision problems that occur in the Round Four algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cannon, J.J., et al.: The computer algebra system Magma. University of Sydney (2010), http://magma.maths.usyd.edu.au/magma/
Cantor, D.G., Gordon, D.: Factoring polynomials over p-adic fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 185–208. Springer, Heidelberg (2000)
Ford, D., Letard, P.: Implementing the Round Four maximal order algorithm. Journal de Théorie des Nombres de Bordeaux 6, 39–80 (1994)
Ford, D., Pauli, S., Roblot, X.-F.: A Fast Algorithm for Polynomial Factorization over ℚ p . Journal de Théorie des Nombres de Bordeaux 14, 151–169 (2002)
Ford, D., Veres, O.: On the Complexity of the Montes Ideal Factorization Algorithm. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS-IX, July 19-23. LNCS, vol. 6197, pp. 174–185. Springer, Heidelberg (2010)
Kaltofen, E., Shoup, V.: Subquadratic-time factoring of polynomials over finite fields. Math. Comp. 67 (1998)
Guardia, J., Montes, J., Nart, E.: Newton polygons of higher order in algebraic number theory (2008), arXiv:0807.2620
Guardia, J., Montes, J., Nart, E.: Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields (2008), arXiv:0807.4065
MacLane, S.: A Construction for absolute values in polynomial rings. Trans. Amer. Math. Soc. 40, 363–395 (1936)
Montes, J., Nart, E.: On a Theorem of Ore. Journal of Algebra 146, 318–334 (1992)
Montes, J.: Polígonos de Newton de orden superior y aplicaciones aritméticas, PhD Thesis, Universitat de Barcelona (1999)
Ore, Ö.: Newtonsche Polygone in der Theorie der algebraischen Körper. Math. Ann. 99, 84–117 (1928)
PARI/GP, version 2.3.4, Bordeaux (2008), http://pari.math.u-bordeaux.fr/
Pauli, S.: Factoring polynomials over local fields. J. Symb. Comp. 32, 533–547 (2001)
Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7, 281–292 (1971)
Stein, W., et al.: SAGE: Software for Algebra and Geometry Experimentation (2007), http://www.sagemath.org
Veres, O.: On the Complexity of Polynomial Factorization over p-adic Fields, PhD Dissertation, Concordia University, Montreal (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pauli, S. (2010). Factoring Polynomials over Local Fields II. In: Hanrot, G., Morain, F., Thomé, E. (eds) Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14518-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-14518-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14517-9
Online ISBN: 978-3-642-14518-6
eBook Packages: Computer ScienceComputer Science (R0)