Paper 2015/1104
Computing Jacobi's \theta in quasi-linear time
Hugo Labrande
Abstract
Jacobi's \theta function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of \theta(z, \tau), for z, \tau verifying certain conditions, with precision P in O(M(P) \sqrt{P}) bit operations, where M(P) denotes the number of operations needed to multiply two complex P-bit numbers. We generalize an algorithm which computes specific values of the \theta function (the theta-constants) in asymptotically faster time; this gives us an algorithm to compute \theta(z, \tau) with precision P in O(M(P) log P) bit operations, for any \tau \in F and z reduced using the quasi-periodicity of \theta.
Note: Corrected a proof in Section 3.4; added proof that the Jacobian is invertible.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- number theoryelliptic curve cryptosystemtheta function
- Contact author(s)
- hugo @ hlabrande fr
- History
- 2016-06-02: revised
- 2015-11-14: received
- See all versions
- Short URL
- https://ia.cr/2015/1104
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/1104,
author = {Hugo Labrande},
title = {Computing Jacobi's \theta in quasi-linear time},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/1104},
year = {2015},
url = {https://eprint.iacr.org/2015/1104}
}
