1. On the complexity of computing integral bases of function fields
- Author
-
Simon Abelard, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Boulier F., England M., Sadykov T.M., and Vorozhtsov E.V.
- Subjects
Algebraic function field ,Computer Science - Symbolic Computation ,FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,050101 languages & linguistics ,Plane curve ,[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC] ,02 engineering and technology ,Symbolic Computation (cs.SC) ,Commutative Algebra (math.AC) ,Puiseux series ,Mathematics - Algebraic Geometry ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Polynomial matrices ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,0501 psychology and cognitive sciences ,Linear algebra ,Algebraic Geometry (math.AG) ,Mathematics ,Discrete mathematics ,[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] ,Irreducible polynomial ,05 social sciences ,Basis (universal algebra) ,Function (mathematics) ,Mathematics - Commutative Algebra ,020201 artificial intelligence & image processing ,[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] ,Monic polynomial - Abstract
Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to B\"ohm et al. and achieve a quasi-optimal runtime., Comment: Preliminary version
- Published
- 2020