Cryptology ePrint Archive: Report 2006/257

Efficient Divisor Class Halving on Genus Two Curves

Peter Birkner

Abstract: Efficient halving of divisor classes offers the possibility to improve scalar multiplication on hyperelliptic curves and is also a step towards giving hyperelliptic curve cryptosystems all the features that elliptic curve systems have. We present a halving algorithm for divisor classes of genus 2 curves over finite fields of characteristic 2. We derive explicit halving formulae from a doubling algorithm by reversing this process. A family of binary curves, that are not known to be weak, is covered by the proposed algorithm. Compared to previous known halving algorithms, we achieve a noticeable speed-up for this family of curves.

Category / Keywords: hyperelliptic curve, divisor class, halving, binary field

Publication Info: Full version

Date: received 31 Jul 2006, last revised 3 Aug 2006

Contact author: peter at mat dtu dk

Available formats: PDF | BibTeX Citation

Version: 20060803:100835 (All versions of this report)

Discussion forum: Show discussion | Start new discussion