Computing Puiseux series: a fast divide and conquer algorithm

Abstract : Let $F ∈ K[X, Y ]$ be a polynomial of total degree D defined over a field K of characteristic zero or greater than D. Assuming F separable with respect to Y , we provide an algorithm that computes all Puiseux series of F above X = 0 in less than $O˜(D δ)$ operations in K, where δ is the valuation of the resultant of F and its partial derivative with respect to Y. To this aim, we use a divide and conquer strategy and replace univariate factorisation by dynamic evaluation. As a first main corollary, we compute the irreducible factors of F in $K[[X]][Y ]$ up to an arbitrary precision X N with $O˜(D(δ + N))$ arithmetic operations. As a second main corollary, we compute the genus of the plane curve defined by F with $O˜(D^3)$ arithmetic operations and, if K = Q, with $O˜((h+1) D^3)$ bit operations using probabilistic algorithms, where h is the logarithmic height of F .
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées
Contributeur : Adrien Poteaux <>
Soumis le : lundi 3 décembre 2018 - 15:34:32
Dernière modification le : mercredi 12 décembre 2018 - 01:22:36


Fichiers produits par l'(les) auteur(s)


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales 4.0 International License


  • HAL Id : hal-01578214, version 3


Adrien Poteaux, Martin Weimann. Computing Puiseux series: a fast divide and conquer algorithm. 2017. 〈hal-01578214v3〉



Consultations de la notice


Téléchargements de fichiers