Cryptology ePrint Archive: Report 2008/265

Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors

Steven D. Galbraith and Michael Harrison and David J. Mireles Morales

Abstract: We discuss arithmetic in the Jacobian of a hyperelliptic curve $C$ of genus $g$. The traditional approach is to fix a point $P_\infty \in C$ and represent divisor classes in the form $E - d(P_\infty)$ where $E$ is effective and $0 \le d \le g$. We propose a different representation which is balanced at infinity. The resulting arithmetic is more efficient than previous approaches when there are 2 points at infinity.

This is a corrected and extended version of the article presented in ANTS 2008. We include an appendix with explicit formulae to compute a very efficient `baby step' in genus 2 hyperelliptic curves given by an imaginary model.

Category / Keywords: foundations / hyperelliptic curves, real models, efficient arithmetic

Publication Info: Extended and corrected version of the ANTS 2008 article.