On the complexity of computing integral bases of function fields

DOI10.1007/978-3-030-60026-6_3MaRDI QIDQ6340298arXivFDO

Authors Simon Abelard

Publication date 8 May 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-60026-6_3

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

arXiv classification

cs.SCmath.ACmath.AG

Abstract: Let $mathcalC$ be a plane curve given by an equation $f(x,y)=0$ with $finK[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(mathcalC)$ 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.

This page was built for publication: On the complexity of computing integral bases of function fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340298)