Fast Jacobian group operations for C_3,4 curves over a large finite field
<|reference_start|>Fast Jacobian group operations for C_3,4 curves over a large finite field: Let C be an arbitrary smooth algebraic curve of genus g over a large finite field K. We revisit fast addition algorithms in the Jacobian of C due to Khuri-Makdisi (math.NT/0409209, to appear in Math. Comp.). The algorithms, which reduce to linear algebra in vector spaces of dimension O(g) once |K| >> g, and which asymptotically require O(g^{2.376}) field operations using fast linear algebra, are shown to perform efficiently even for certain low genus curves. Specifically, we provide explicit formulae for performing the group law on Jacobians of C_{3,4} curves of genus 3. We show that, typically, the addition of two distinct elements in the Jacobian of a C_{3,4} curve requires 117 multiplications and 2 inversions in K, and an element can be doubled using 129 multiplications and 2 inversions in K. This represents an improvement of approximately 20% over previous methods.<|reference_end|>
@article{salem2006fast,
    title={Fast Jacobian group operations for C_{3,4} curves over a large finite
  field},
    author={Fatima K. Abu Salem (Computer Science Department, American University
  of Beirut) and Kamal Khuri-Makdisi (Center for Advanced Mathematical
  Sciences, American University of Beirut)},
    journal={LMS J. Comput. Math. 10 (2007) 307-328, may be downloaded from
  http://www.lms.ac.uk/jcm/10/lms2006-049/},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0610121},
    primaryClass={math.NT cs.SC math.AG}
}