Fast Scalar Multiplications on the Curve v2= up − au − b over the Finite Field of Characteristic p

Hyperelliptic curves have been widely researched for cryptographic applications, and some special hyperelliptic curves are often considered for practical applications. For efficient implementation of hyperelliptic curve cryptosystems, it is crucial to have efficient scalar multiplication in the Jacobian groups. For the hyperelliptic curve Cq: v2= up − au − b over the field Fq with q a power of an odd prime p, Duursma and Sakurai (2000) presented a scalar multiplication algorithm for q = p, a = 1 and b ∈ Fp. In this paper, by introducing the concept of simple divisors, we prove that a general divisor can be decomposed into the sum of some simple divisors. Based on this fact, we present a formula for p-scalar multiplications for any reduced divisor, then we give two efficient algorithms to speed up scalar multiplications for any parameters a and b over any extension of Fp. Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less.