基于p^k进制的一类超椭圆曲线上标量乘算法

p^k-ary Based Fast Scalar Multiplication Algorithms on a Class of Hyperelliptic Curves

超椭圆曲线密码体制中,除子标量乘算法是提高密码算法运算效率的关键运算。该文将正整数的p进制以及pk进制表示相结合,提出了基于一类超椭圆曲线Cq:v2=up+au+b上的快速标量乘算法。讨论了3种标量乘算法:以p=3为特例与滑动窗口法结合的p进制算法,pk进制算法以及与已有算法结合后改进的pk进制算法。最后从除子加与倍加运算角度出发,给出了3种法与二进制算法在运算量与运算效率方面的比较。通过对比可知,p进制算法可使运算量明显减少,当p=7时,减少量约为64.4%。

Scalar multiplication is the most important operation in HECC.By discussing p-ary algorithm on a class of hyperelliptic curves Cq：v2=up＋au＋b,this paper presents three scalar multiplication algorithms,namely p-ary algorithm with p=3as special case,pk-ary algorithm and the improved pk-ary algorithm.It shows the respective advantages of these three algorithms on divisor additions and divisor doublings.Compared with the binary method,p-ary algorithm can saves about 64.4% of the calculation amount of divisors additions in case of p=7.