Fast Tripling In Genus 2 Hyperelliptic Curves

Abstract

We describe explicit formulas for tripling divisor classes on imaginary hyperelliptic curves given in Weierstrass form over arbitrary finite fi elds. Formulas are presented for both a ffine and projective coordinates, for divisor classes whose representations have extra fi eld elements, and for simpli fied forms of the curve equation. By combining ideas from the algebraic and geometric methods we obtain savings compared to previous methods. The same methods are applied to addition and doubling, resulting in the fastest known formulas to-date.