论文标题
关于计算功能字段积分基础的复杂性
On the complexity of computing integral bases of function fields
论文作者
论文摘要
令$ \ mathcal {c} $为公式$ f（x，y）= 0 $给出的平面曲线，而$ f \ in k [x] [y] $ a monic Squarefree多项式。我们研究了计算代数函数字段$ k（\ Mathcal {C}）$不可或缺的基础的问题，并为解决此问题的三种已知算法提供了新的复杂性界限。对于每种算法，我们研究其子例程，并在可能的情况下修改或替换它们，以利用更快的原始剂。然后，我们结合了复杂性结果，以得出每种算法的总体复杂性估计。特别是，由于Böhm等人，我们修改了一种算法。并实现准最佳运行时。
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öhm et al. and achieve a quasi-optimal runtime.
