Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator

Alin Bostan 1 Pierrick Gaudry 2, 3 Eric Schost 4
1 ALGO - Algorithms
Inria Paris-Rocquencourt
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
3 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the complexity of computing one or several terms (not necessarily consecutive) in a recurrence with polynomial coefficients. As applications, we improve the best currently known upper bounds for factoring integers deterministically, and for computing the Cartier-Manin operator of hyperelliptic curves.
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2007, 36 (6), pp.1777-1806. 〈10.1137/S0097539704443793〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00103401
Contributeur : Pierrick Gaudry <>
Soumis le : mardi 27 mars 2007 - 09:38:43
Dernière modification le : mardi 17 avril 2018 - 11:34:41
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 16:14:12

Fichier

pollard-final.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Alin Bostan, Pierrick Gaudry, Eric Schost. Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2007, 36 (6), pp.1777-1806. 〈10.1137/S0097539704443793〉. 〈inria-00103401v3〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

241