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.

Date: received 11 Jun 2008

Contact author: david mireles at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20080618:121813 (All versions of this report)

Short URL: ia.cr/2008/265

Discussion forum: Show discussion | Start new discussion