Affiliations: College of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China. mryoulin@gmail.com; ylyangapple@hotmail.com | Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA. sgao@clemson.edu | College of Communication Engineering, Hangzhou Dianzi University, Hangzhou, China. sangyongxuan@126.com
Note: [] Address for correspondence: College of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China
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 Cq: v2 = up − 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.
Keywords: Hyperelliptic curve, Cryptosystem, Scalar Multiplications, Divisor, Jacobian Group
