STNB2022 (35th edition)
Local polynomial factorisation: improving the Montes algorithm
Presenters
Adrien Poteaux
Abstract
This talk will present a new divide and conquer strategy to improve the complexity of the Montes algorithm. To do so, we show how to adapt the Hensel lemma in the context of generalised Newton polygon. Finally, we show that using approximate roots (when they exist) as representatives of a type improves the irreducibility test, and also the factorisation algorithm when combined with our generalised Hensel lemma. For instance, given $F\in\mathbb{Z}_p[x]$ with $p$ small, we compute its OM-factorisation in $O(d^{1+\epsilon}\,\delta^{1+\epsilon})$ operations over $\mathbb{F}_p$ if $d$ denotes its degree and and $\delta$ its discriminant valuation. We will also briefly present the Newton-Puiseux algorithm as an introduction and its connection with the Montes algorithm.
Files
