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.