Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator
Résumé
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.
Domaines
Cryptographie et sécurité [cs.CR]
Origine : Fichiers éditeurs autorisés sur une archive ouverte