Computing theta functions in quasi-linear time in genus 2 and above

Hugo Labrande 1, 2 Emmanuel Thomé 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We outline an algorithm to compute θ(z, τ) in genus 2 in quasi-optimal time, borrowing ideas from the algorithm for theta constants and the one for θ(z, τ) in genus 1. Our implementation shows a large speedup for precisions as low as a few thousand decimal digits. We also lay out a strategy to generalize this algorithm to genus g.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download
Contributor : Hugo Labrande <>
Submitted on : Monday, February 22, 2016 - 11:41:50 AM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Long-term archiving on : Sunday, November 13, 2016 - 12:20:13 AM


Files produced by the author(s)




Hugo Labrande, Emmanuel Thomé. Computing theta functions in quasi-linear time in genus 2 and above. LMS Journal of Computation and Mathematics, London Mathematical Society, 2016, Special issue: Algorithmic Number Theory Symposium XII, 19 (A), pp.163-177. ⟨10.1112/S1461157016000309⟩. ⟨hal-01277169⟩



Record views


Files downloads