Local Polynomial Factorisation: Improving the Montes Algorithm
Local Polynomial Factorisation: Improving the Montes Algorithm
复制标题
局部多项式因式分解：改进 Montes 算法
DOI：
10.1145/3476446.3535487
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Martin Weimann
中科院分区：
文献类型：
--
作者：
A. Poteaux;Martin Weimann
本文改进了完全离散赋值环A上多项式因式分解的Nart-Montes算法。我们的第一个贡献是广义牛顿多边形的背景下，我们从中获得一个新的分而治之的战略，扩展的Hensel引理。此外，如果A有剩余特征零或足够高，我们证明了近似根是方便的代表类型，最终导致几乎最佳的复杂性，无论是不可约化和因式分解问题，加上成本因式分解以上的剩余字段。例如，为了计算F∈A[x]的OM-因子分解，我们通过因子δ改进了[3]的复杂性结果，因子δ是F的判别赋值。
We improve significantly the Nart-Montes algorithm for factoring polynomials over a complete discrete valuation ring A. Our first contribution is to extend the Hensel lemma in the context of generalised Newton polygons, from which we derive a new divide and conquer strategy. Also, if A has residual characteristic zero or high enough, we prove that approximate roots are convenient representatives of types, leading finally to an almost optimal complexity both for irreducibility and factorisation issues, plus the cost of factorisations above the residue field. For instance, to compute an OM-factorisation of F∈A[x], we improve the complexity results of [3] by a factor δ, the discriminant valuation of F.