Fast Scalar Multiplications on the Curve v 2 = u p − au − b over the Finite Field of Characteristic p

Abstract

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 C_q: v² = u^p − au − b over the field $\Fopf_{q}$ 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 ∈ $\Fopf_{p}$. 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 $\Fopf_{p}$. Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less.