Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
Alin Bostan, Pierrick Gaudry, Éric Schost · SIAM Journal on Computing · 2007
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.