Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves

Abstract : We improve an algorithm originally due to Chudnovsky and Chudnovsky for computing one selected term in a linear recurrent sequence with polynomial coefficients. Using baby-steps / giant-steps techniques, the nth term in such a sequence can be computed in time proportional to sqrt(n), instead of n for a naive approach. As an intermediate result, we give a fast algorithm for computing the values taken by an univariate polynomial P on an arithmetic progression, taking as input the values of P on a translate on this progression. We apply these results to the computation of the Cartier-Manin operator of a hyperelliptic curve. If the base field has characteristic p, this enables us to reduce the complexity of this computation by a factor of order sqrt(p). We treat a practical example, where the base field is an extension of degree 3 of the prime field with p = 2^32 − 5 elements.
Type de document :
Communication dans un congrès
Gary L. Mullen and Alain Poli and Henning Stichtenoth. Finite Fields and Applications - Fq7, 2004, Toulouse, France. Springer Verlag, 2948, pp.40-58, 2004, LNCS. 〈10.1007/978-3-540-24633-6_4〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00514132
Contributeur : Pierrick Gaudry <>
Soumis le : mercredi 1 septembre 2010 - 13:03:45
Dernière modification le : mercredi 25 avril 2018 - 10:45:38
Document(s) archivé(s) le : jeudi 2 décembre 2010 - 02:45:06

Fichier

cartier.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alin Bostan, Pierrick Gaudry, Éric Schost. Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves. Gary L. Mullen and Alain Poli and Henning Stichtenoth. Finite Fields and Applications - Fq7, 2004, Toulouse, France. Springer Verlag, 2948, pp.40-58, 2004, LNCS. 〈10.1007/978-3-540-24633-6_4〉. 〈inria-00514132〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

116