The irreducible factorization of polynomials over power series is central to several problems in computer algebra: integral bases, genus of a curve, Jacobian of a curve, Riemann–Roch spaces. Well-known applications include cryptography and algebraic geometry error-correcting codes. Towards solving these problems with quasi-optimal complexity, recent algorithms make use of the so-called “contact representation”. When carrying out the Newton polygon method, this allows intermediate objects to be represented in a compact way with respect to the required relative precision. In this paper, we focus on the complexity of the corresponding “contact arithmetic” and present quasi-optimal algorithms for multiplication and division in the contact representation.

Authors: Joris van der Hoeven, Grégoire Lecerf

View: Html, TeXmacs, Pdf, BibTeX