Paper 2008/265

Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors

Steven D. Galbraith, 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_{\mathrm{\infty }}\in C$ and represent divisor classes in the form $E-d(P_{\mathrm{\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.