Efficient Explicit Formulae for Genus 2 Hyperelliptic Curves over Prime Fields and Their Implementations
Efficient Explicit Formulae for Genus 2 Hyperelliptic Curves over Prime Fields and Their Implementations
复制标题
DOI：
10.1007/978-3-540-77360-3_11
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
Xinxin Fan;G. Gong
中科院分区：
文献类型：
--
作者：
Xinxin Fan;G. Gong
我们分析了所有的情况，并给出了在素数域上定义的属2超椭圆曲线上从给定的因子类d1和d2一步计算2D1+ d2的相应显式公式。与朴素方法相比，改进公式在最频繁的情况下，每次可节省2次域乘法和1次域平方。此外，我们提出了一种变体，通过使用Montgomery的技巧将两种反转结合起来，将一个场反转转换为14个场乘法和两个场平方。实验结果表明，该算法在素数域上对一般的2属超椭圆曲线进行标量乘法运算的时间，比目前已知的一般方法节省了13%。
We analyze all the cases and propose the corresponding explicit formulae for computing 2D1+D2in one step from given divisor classesD1andD2on genus 2 hyperelliptic curves defined over prime fields. Compared with naive method, the improved formula can save two field multiplications and one field squaring each time when the arithmetic is performed in the most frequent case. Furthermore, we present a variant which trades one field inversion for fourteen field multiplications and two field squarings by using Montgomery’s trick to combine the two inversions. Experimental results show that our algorithms can save up to 13% of the time to perform a scalar multiplication on a general genus 2 hyperelliptic curve over a prime field, when compared with the best known general methods.