Cryptology ePrint Archive: Report 2016/179

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

Hugo Labrande and Emmanuel Thomé

Abstract: We outline an algorithm to compute $\theta(z,\tau)$ in genus 2 in quasi-optimal time, borrowing ideas from the algorithm for theta constants and the one for $\theta(z,\tau)$ 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$.

Category / Keywords: public-key cryptography / number theory, hyperelliptic curves, theta functions

Date: received 22 Feb 2016

Contact author: hugo at hlabrande fr

Available format(s): PDF | BibTeX Citation

Version: 20160222:213817 (All versions of this report)

Short URL: ia.cr/2016/179

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]