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
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00103401
Contributor : Pierrick Gaudry <>
Submitted on : Tuesday, March 27, 2007 - 9:38:43 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Thursday, September 23, 2010 - 4:14:12 PM

File

pollard-final.pdf
Publisher files allowed on an open archive

Identifiers

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⟩

Share

Metrics

Record views

407

Files downloads

490