亏格2超椭圆曲线除子类群的直接算法

Formulae Derived by NUCOMP Algorithm for Arithmetic on Genus 2

针对亏格2超椭圆曲线的情形,从以下三方面改进了NUCOMP算法:(1)用有限域Fq中元素的求逆运算代替NUCOMP算法中的多项式求逆运算;(2)利用Montgomery的求逆技巧将多个元素求逆用一个元素求逆实现;(3)在NUCOMP算法计算中省去了部分多项式的系数计算.实验结果表明,改进后的算法比NUCOMP算法效率显著提高。

We used the following technique to improve the NUCOMP algorithm for the hyperelliptic curves of genus 2：（1） avoiding the computation of the polynomial＇s inverse by resultant;（2） Montgomery＇s trick of simultaneous inversions;（3） Reordering of normalization steps to save some field operations.The experimental results show that our algorithm is more efficient than the NUCOMP algorithm.