Abstract: In hyperelliptic curve croptosystem, the most important and computationally costliest operation is the scalar multiplication. To speed up, an efficient algorithm for simultaneously obtaining the inverses of a list of underlying field elements is given. The feature of the algorithm is that the later arithmetics make efficient use of the results of the former ones. The algorithm decreases the number of arithmetics and saves time. The scalar multiplication algorithm with the efficient algorithm for inversion is 32%~35% faster than the scalar multiplication algorithm given by Lange and 49%~53% or 6%~7% faster than the improved scalar multiplication algorithms given by Mishra and others, and provides protection agatinst side-channel attacks.

Key words: hyperelliptic curves, public key cryptosystems, scalar multiplication, field element inversion, divisor