# Fast scalar multiplications on hyperelliptic curve cryptosystems.

Scalar multiplication is the key operation in hyperelliptic curve cryptosystem. By making use of Euclidean lengths of algebraic integral numbers in a related algebraic integer ring, we discuss the Frobenius expansions of algebraic numbers, theoretically and experimentally show that the multiplier in a scalar multiplication can be reduced and converted into a Frobenius expansion of length approximate to the field extension degree, and then propose an efficient scalar multiplication algorithm. Our method is an extension of the results given by Muller, Smart and Gunther et al. If some (optimal) normal basis is employed, then, for some hyperelliptic curves over finite fields, our method will make the computations of scalar multiplications be lessened about fifty-five percent compared with the signed binary method.

Keywords: Hyperelliptic Curve cryptosystems, scalar multiplications, Frobenious Endomorphism, Frobenious Expansion, Euclidean length

Povzetek: Predstavljena je metoda pohitrenega skalarnega mnozenja.

1 Introduction

Elliptic curve cryptosystems (ECC) have now widely been studied and applied in e-commerce, e-government and other secure communications. The practical advantages of ECC is that it can be realized with much smaller parameters compared to the conventional discrete logarithms based cryptosystems or RSA but with the same levels of security. This advantage is especially important in the environments with limited processing power, storage space and bandwidth.

As a natural generalization of elliptic curve cryptosystems, the hyperelliptic curve cryptosystem (HECC) was first proposed by Koblitz (1; 2). In a hyperelliptic curve cryptosystem, the rational point group of an elliptic curve, is replaced by the Jacobian group of a hyperelliptic curve, and its security is based on the discrete logarithm on this Jacobian group, that is, based on the hyperelliptic curve discrete logarithm problems(HECDLP). Since the order of the Jacobian group can be constructed much large over a small base field in HECC, HECC has gotten much attention in cryptography, a lot of work has been done to study the group structures and operations on the Jacobian groups.

Let q be a power of some prime and [F.sub.q] be the finite field of q elements. A hyperelliptic curve C of genus g over [F.sub.q] is defined by the equation

[v.sup.2] + h(u)v = f(u), (1)

where h(u), f(u) [member of] [F.sub.q] with [deg.sub.u](h) [less than or equal to] g and [deg.sub.u](f) = 2g + 1, and there is no solution (u, v) [member of] [[bar.F].sub.q] x [[bar.F].sub.q] which simultaneously satisfy the equation [v.sup.2] + h(u)v = f(u) and the partial derivate equations 2v + h(u) = 0 and h'(u)v - f'(u) = 0. If the characteristic of [F.sub.q] is odd, then the curve (1) is isomorphic to a hyperelliptic curve with the corresponding h(u) equal to 0.

A divisor D on C over [F.sub.q] is defined as a finite formal sum of rational [[bar.F].sub.q]-points D = [summation][m.sub.i][P.sub.i] on C with its degree defined as the integer [summation][m.sub.i]. The Jacobian group [J.sub.C]([F.sub.q]) of the curve C over [F.sub.q] is an Abelian group composed of reduced divisors on C. Every element or reduced divisor D in [J.sub.C]([F.sub.q]) can be uniquely expressed by a pair of polynomials < a(u), b(u) > with the properties

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2)

where a(u), b(u) [member of] [F.sub.q][u]. Generally, a(u) is a monic polynomial of degree g and b(u) is a polynomial of degree g - 1 with a overwhelming probability. The zero element of [J.sub.C]([F.sub.q]) can be expressed as < 1, 0 >.

In practical hyperelliptic curve cryptosystems, the vital computation that dominates the whole running time is scalar multiplication, that is, the computation of the repeated divisor adding

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for a given divisor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a positive integer m [greater than or equal to] 1, which is denoted as mD.

Such as in the hyperelliptic curve Diffie-Hellman key exchange protocol(HECDH), suppose Alice and Bob wish to generate their shared secret key for their secure communication, then they do the followings:

--First they agree on a positive integer n and a hyperelliptic curve C over a finite field [F.sub.q], and also a divisor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

--Alice randomly chooses an positive integer [m.sub.A] that is smaller than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and then compute the scalar multiplication [D.sub.A] = [m.sub.A]D and send [D.sub.A] to Bob.

--Bob similarly chooses an positive integer [m.sub.B], compute [D.sub.B] = [m.sub.B]D and send [D.sub.B] to Alice.

--Alice and Bob compute the scalar multiplications [D.sub.A,B] = [m.sub.A][D.sub.B] and [D.sub.B,A] = [m.sub.B][D.sub.A], respectively.

--Since [D.sub.A,B] = [m.sub.A][D.sub.B] = [m.sub.A]([m.sub.B]D) = ([m.sub.A][m.sub.B])D = ([m.sub.B][m.sub.A])D = [D.sub.B,A], Alice and Bob get their shared secret key [D.sub.A,B].

--Using this shared secret key [D.sub.A,B] and some symmetric cryptographic algorithm of their choice, Alice and Bob can communicate securely.

As the above shown, each of Alice and Bob compute two scalar multiplications and the scalar multiplication is the unique operation that involved in HECDH. Also in the hyperelliptic curve digital signature algorithm(HECDSA), it takes three dominating scalar multiplications except for some simple field operations.

A natural algorithm to compute the scalar multiplication mD is (signed) binary method. In (6; 7), Muller and Smart employed Frobenius automorphism to compute point scalar multiplications on elliptic curves over small fields of characteristic even or odd, respectively. In (8), Gunther et al employed Frobenius automorphism to compute scalar multiplications on two hyperelliptic curves of genus 2. Their ideas are based on the two facts: One is that, for a point or divisor D, computing [phi](D) is much faster than doubling D, and the other is that every Z[[tau]]-integer can be represented as Frobenius expansion or [tau]-adic expansion of finite lengths, where [tau] is a root of P(T). In this paper, we will extend their methods to compute scalar multiplications on hyperelliptic curves of general genus.

The remainder of this paper is organized as follows: In Section 2, we briefly describe the Frobenius endomorphism on Jacobian groups of hyperelliptic curves over finite fields and a lemma contributed to Weil's theorem((5)), and in this section, we also introduce the Euclidean length in the algebraic integral ring Z[[tau]] with [tau] a root of some hyperelliptic curve's characteristic polynomial. In Section 3, we discuss the lengths of [tau]-adic expansions of algebraic integral numbers in Z[[tau]] and obtain an upper bound for them. In Section 4, we study the cyclic [tau]-adic expansions and the optimization of the [tau]-expansions's lengths. The [tau]-expansion's length of any algebraic integral number is optimized in Section 5, An efficient scalar multiplication algorithm is proposed in Section 6, and the last section gives the conclusion.

2 Frobenius endomorphism over Jacobian groups of hyperelliptic curves

The Frobenius map [phi] of [[bar.F].sub.q] is defined as the map x [right arrow] [x.sup.q] for x [member of] [[bar.F].sub.q]. Naturally, [phi] induces an endomorphism [[phi].sub.J] of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a reduced divisor or an element of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For convenience, [[phi].sub.J] is also denoted by [phi].

Lemma 1((5)) For any positive integer r, let [M.sub.r] denote the number of rational points of the hyperelliptic curve C defined by Equation (1) over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the order of the Jacobian group [J.sub.C]([F.sub.q]). Then

1. The zeta-function Z(t) has the expression

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where L(t) is an integral coefficient polynomial of degree 2g.

2. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then [absolute value of [[tau].sub.i]] = [square root of q], and the roots come in complex conjugate pairs such that there exists an ordering with [[tau].sub.i+g] [[bar.[tau]].sub.i], and hence, [[tau].sub.i+g][[tau].sub.i] = q.

3. P(T) is the characteristic polynomial of Frobenius endomorphism [phi] and P(T) is an integral coefficient polynomial of the following form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

4. Let [a.sub.0] = 1, then for 1 [less than or equal to] i [less than or equal to] g

[ia.sub.i] = ([M.sub.i] - [q.sup.i] - 1)[a.sub.0] + ([M.sub.i-1] - [q.sup.i-1] - 1)[a.sub.1] + ... + ([M.sub.1-q] - 1)[a.sub.i-1].

5. For any positive integer n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For cryptographic purposes, in order to resist all possible attacks on the HECDLP, such as Pollardars rho algorithm((3)) and Pohlig-Hellman algorithm((4) or their improved versions, it is most desirable that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have a large prime integer factor, or to the best, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is by itself a large prime or almost large prime. For the best possibility, the necessary condition is that P(T) is irreducible. Hence, P(T) is assured to be irreducible here.

3 Euclidean lengths in the algebraic integral ring Z[[tau]]

Let C be a hyperelliptic curve of genus g over [F.sub.q] with the characteristic polynomial (3). Let [tau] be a root of P(T). Then, since P(T) is irreducible, every element [xi] in Z[[tau]] can be uniquely expressed as the form

[x.sub.0] + [x.sub.1][tau] + ... + [x.sub.2g-1][[tau].sup.2g-1].

Let [tau] = [[tau].sub.1], [[tau].sub.2], ..., [[tau].sub.g] be the g roots of P(T) which are not conjugate each other. Then, we can define a positive number N([xi]) corresponding to [xi] as the following

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [absolute value of x] denotes the complex absolute value of x. N([xi]) is often called the Euclidean length of [xi].

It is clear that N([xi][eta]) [less than or equal to] N([xi])N([eta]) and N([xi] + [eta]) [less than or equal to] N([xi]) + N([eta]) hold for any [xi], [eta] [member of] Z[[tau]]. And N[([xi]).sup.2] is a positive definite quadratic form in the variables [x.sub.0], [x.sub.1], ..., [x.sub.2g-1], with the coefficients being integer polynomials of P(T)'s coefficients [a.sub.i](1 [less than or equal to] i [less than or equal to] g).

For g = 1 and [xi] = [x.sub.0] + [x.sub.1][tau], we have

N[([xi]).sup.2] = [x.sup.2.sub.0] - [a.sub.1][x.sub.0][x.sub.1] + q[x.sup.2.sub.1].

For g = 2 and [xi] = [x.sub.0] + [x.sub.1][tau] + [x.sub.2][[tau].sup.2] + [x.sub.3][[tau].sup.3], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In general, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then we can easily prove

N[([xi]).sup.2] = XA[X.sup.T],

where [S.sub.i] can be computed by the following Newton's formula:

[S.sub.i] + [a.sub.1][S.sub.i-1] + [a.sub.2][S.sub.i-2] + ... + [a.sub.i-1][S.sub.1] + i[a.sub.i] = 0

with [a.sub.0] = 1 and [a.sub.j] = [a.sub.2g-j][q.sup.j-g] for j > g.

4 Convert m into [tau]-adic expansion

Similar to Lemma 1 in (6), we have

Lemma 2 (Division With Remainder in Z[[tau]]) Let m [member] Z[[tau]], then there exists a unique pair of elements m' and r such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Theorem 1 Let m [member of] Z[[tau]], then m can be uniquely represented as a [tau]-adic expansion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof Iterate the Division With Remainder in Z[[tau]] for [m.sub.0] = m, then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence,

[m.sub.0] = [j-1.summation over i=0][r.sub.i][[tau].sup.i] + [m.sub.j][[tau].sup.j].

Apply triangle inequality for Euclidean length in [m.sub.i] = [m.sub.i+1][tau] + [r.sub.i], and we will get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 3 [a.sub.1] [less than or equal to] 2 [??]2[square root of q][??]. And if [a.sub.2] = 0, then

[absolute value of [a.sub.1]] < [square root of q].

Proof [a.sub.1] [less than or equal to] 2 [??]2[square root of q][??] holds obviously since every root of P(T) has the complex absolute value [square root of q]. If [a.sub.2] = 0, then [absolute value of [a.sub.1]] < [square root of q] follows the facts [M.sub.2] - [q.sup.2] - 1 + [a.sup.2.sub.1] = 0 and [M.sup.2] > 1.

Lemma 4 If C is a hyperelliptic curve of genus 2 with the irreducible characteristic polynomial P(T) = [T.sup.4] + [a.sub.1][T.sup.3] + [a.sub.2][T.sup.2] + [a.sub.1]qT + [q.sup.2], then [a.sup.2.sub.1] - 4[a.sub.2] + 8q is non-square and

2[absolute value of [a.sub.1]][square root of q] - 2q < [a.sub.2] < [a.sup.2.sub.1]/4 + 2q.

Proof If [a.sup.2.sub.1] - 4[a.sub.2] + 8q is square, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which contradicts our hypothesis that P(T) is irreducible.

Due to (9), we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and it follows 2[absolute value of [a.sub.1]][square root of q] - 2q < [a.sub.2] < [a.sup.2.sub.1]/4 + 2q.

Theorem 2 Let C be a hyperelliptic curve of genus g and its irreducible characteristic polynomial P(T) have a root [tau]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and a [tau]-adic expansion means a [tau]-polynomial with the coefficients belong to R. Let [xi] [member of] Z[[tau]] with

N([xi]) < [q.sup.g][square root of g]/2([square root of q] - 1). (5)

1. If g = 2, [a.sub.1] = [a.sub.2] = 0, then for every positive integer m, m has a [tau]-adic expansion of length about 1/2 [??][log.sub.q]m[??]. (But, in this case, the curves are supersingular and not suitable for cryptosystems).

2. If g = 2, and only one of [a.sub.1] and [a.sub.2] equal to 0, then [xi] has a [tau]-adic expansion of length at most 5.

3. If g = 2, and none of [a.sub.1] and [a.sub.2] equals to 0, then [xi] has a [tau]-adic expansion of length at most 8.

4. If 9 [greater than or equal to] 3, then [xi] has a [tau]-adic expansion of length l [less than or equal to] 2g + 4.

Proof Suppose [xi] [member of] Z[[tau]] satisfying the inequality (5), then

N[([xi]).sup.2] < g[q.sup.2g]/4[([square root of q] - 1).sup.2].

1. Since [q.sup.2] + [[tau].sup.4] = 0 or [q.sup.2] = -[[tau].sup.4], it obviously follows that m has a [tau]-adic expansion of length about 1/2 [??][log.sub.q] m[??].

2. Suppose [a.sub.1] = 0. Then [absolute value of [a.sub.2]] < 2q, and it follows 4[q.sub.2] - [a.sup.2.sub.2] [greater than or equal to] 4q - 1. Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (7)

and so,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

a) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a [tau]-adic expansion of length at most 5.

b) If q [greater than or equal to] 4 and [absolute value of [x.sub.0]] [greater than or equal to] [q.sup.2]/2, then [xi] is itself a [tau]-adic expansion of length 4.

c) If q = 2, then [a.sub.2] = [+ or -] 1. Hence, from (7), we have [absolute value of [x.sub.0]] [less than or equal to] 4, [absolute value of [x.sub.1]] [less than or equal to] 3, [absolute value of [x.sub.2]] [less than or equal to] 2 and [absolute value of [x.sub.3]] [less than or equal to] 1. If [absolute value of [x.sub.0]] [less than or equal to] 2 and [absolute value of [x.sub.1]] [less than or equal to] 2, then [xi] is itself a [tau]-adic expansion. If [absolute value of [x.sub.0]] [less than or equal to] 2 and [absolute value of [x.sub.1]] = 3, then [xi] = [x.sub.0] + ([x.sub.1] [+ or -] 4)[tau] + [x.sub.2][[tau].sup.2] + ([x.sub.3] [+ or -] 1)[[tau].sup.3] - [[tau].sup.4] is a [tau]-adic expansion of length l [less than or equal to] 5.

If [absolute value of [x.sub.0]] = 3, then from (6), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (8)

which implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a [tau]-adic expansion of length 5.

If 0 < [absolute value of [x.sub.1]] [less than or equal to] 2 and [x.sub.3] = 0, then [xi] is itself a [tau]-adic expansion or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a [tau]-adic expansion of length l [less than or equal to] 5.

If 0 < [absolute value of [x.sub.1]] [less than or equal to] 2 and [absolute value of [x.sub.3]] = 1, then from the equation (8) we obtain [absolute value of [x.sub.2]] [less than or equal to] 1. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a [tau]-adic expansion of length l [less than or equal to] 5.

If [absolute value of [x.sub.0]] = 4, then from (6), we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, [xi] is a [tau]-adic expansion of length l [less than or equal to] 4.

d) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3. Suppose [a.sub.2] = 0. Then by Lemma 3, [absolute value of [a.sub.1]] = 1 for q = 2,3 and [absolute value of [a.sub.1]] < [square root of q] for q > 3. Since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (9)

it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

Similarly, we will get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

If q [greater than or equal to] 4 then [absolute value of [x.sub.1]] [less than or equal to] [q.sup.2]/2 for i = 0, 1, 2, 3. Hence, [xi] is a [tau]-adic expansion of length at most 4.

Let q = 3, then from (9), (10), (11) and (12), we have [absolute value of [x.sub.0]] [less than or equal to] 7, [absolute value of [x.sub.1]] [less than or equal to] 3, [absolute value of [x.sub.2]] [less than or equal to] 1 and [absolute value of [x.sub.3]] [less than or equal to] 1. Without loss of generality, suppose [a.sub.1] = 1 and [x.sub.0] > 0, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a [tau]-adic expansion of length at most 5.

Similar discussion will show that ~ can also be represented as a [tau]-adic expansion of length at most 5 for q = 2.

4. Suppose [a.sub.1] [not equal to] 0 and [a.sub.2] [not equal to] 0. Then for [xi] = [x.sub.0] + [x.sub.1][tau] + [x.sub.2][[tau].sup.2] + [x.sub.3][[tau].sup.3], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

If [a.sub.2] = 2q + [a.sup.2.sub.1]/4 or [a.sub.1] = [+ or -](2q + [a.sub.2])/(2[square root of q]), then F = 0, which contradicts F [greater than or equal to] 1. While, it is very likely that H/F or G/F takes maximal values at [a.sub.2] = 2q + [a.sup.2.sub.1]/4 - [theta] or -2q + 2[absolute value of [a.sub.1]][square root of q] + [delta], where [theta] = 1 or 1/4, [delta] = 1 or [??][absolute value of [a.sub.1]][square root of q][??] - 2[absolute value of [a.sub.1]][square root of q].

According to (10), if C is a curves with [a.sub.2] = 2q + ([a.sup.2.sub.1] - 1)/4, then it may not be a hyperelliptic curve. Thus, we do not consider this case.

i) Let [a.sub.2] = 2q + [a.sup.2.sub.1]/4 - 1. Then, if [a.sub.1] [not equal to] [+ or -](4[square root of q] - 2), H/F and G/F are strictly increasing or decreasing with [a.sub.1] > 0 or [a.sub.1] < 0. Hence, if q is a square, then H/F and G/F reach their maximal values at [a.sub.1] = [+ or -] (4[square root of q] - 4), that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively. Thus, H/F < 3/5[q.sup.-1/2] and G/F < 3[square root of q]. If q is non-square, without loss of generality, suppose [a.sub.1] [greater than or equal to] 2. Because both H/F and G/F are strictly increasing functions of [a.sub.1] except in a neighborhood of [a.sub.1] = 4[square root of q] - 2, they will reach their possible maximal values at [a.sub.1] = 2(2[square root of q] - [xi]) - 2 since [a.sub.1] [less than or equal to] 2 [??]2[square root of q][??] and [a.sub.1] is even, where [epsilon] = 2[square root of q] - [??]2[square root of q][??]. Replace [a.sub.1] and [a.sub.2] in H/F with 2(2[square root of q] - [epsilon]) - 2 and 2q + [a.sup.2.sub.1]/4 - 1, respectively. Then, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

ii) Let q be square and [a.sub.2] = -2q + 2[absolute value of [a.sub.1]][square root of q] + 1. Without loss of generality, suppose [a.sub.1] [greater than or equal to] 1. Since [a.sub.2] < [a.sup.2.sub.1]/4 + 2q, it follows [a.sub.1] [less than or equal to] 4[square root of q] - 3. It is easy to show that H/F is strictly increasing for 1 [less than or equal to] [a.sub.1] [less than or equal to] 4[square root of q] - 3. Hence, H/F will reach its maximal value at [a.sub.1] = 4[square root of q] - 3, and so, H/F < 4/5 [q.sup.-1/2]. Similar discussion will induce G / F < 27/5[q.sup.1/2].

iii) Let [a.sub.2] = -2q + 2[absolute value of [a.sub.1]][square root of q] + [delta] with [delta] = [??]2[absolute value of [a.sub.1]][square root of q][??] - 2[absolute value of [a.sub.1]][square root of q] (q is non- square). Still suppose [a.sub.1] [greater than or equal to] 1. Then, [a.sub.1] < 4[square root of q] - 2[square root of [delta]]. Let [a.sub.1] = 4[square root of q] - 2 + [epsilon], where 0 < [epsilon] < 1 such that [a.sub.1] is an integer, that is, [a.sub.1] = [??]4[square root of q] - 2[??]. Replace [a.sub.1] and [a.sub.2] in H/F with 4[square root of q] - 2 + [epsilon] and -2q + 2[a.sub.1] [square root of q] + [delta], respectively. Then, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similar discussion will induce G/F [approximately equal to] 9/2[square root of q][[delta].sup.-1] < 18q.

From all the discussion above, we conclude that if [a.sub.2] [not equal to] 2q + ([a.sup.2.sub.1] - 1)/4, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence, if q is square, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and if q is non-square, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the following discussions, without loss of generality, we assure [a.sub.1] > 0 and [x.sub.0] > 0. And, for the worst case, we also assume that all [x.sub.i] is near to its upper bound. Then, if q is a square no less than 49 and [a.sub.2] > 0(similar discussion for [a.sub.2] < 0), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which implies that [xi] is a [tau]-adic expansion of length at most 7, where [d.sub.0] is an integer close to 2/[square root of 5][q.sup.1/4] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By almost the same discussions, we will show that [xi] can be expressed as a [tau]-adic expansion of length at most 8 if q is a non-square no less than 37.

If q is a square smaller than 25 or a non-square smaller than 31, then [xi] may go to a cyclic [tau]-adic expansion with the coefficients in R. But, we can easily show that if [a.sub.2] [not equal to] 2q + ([a.sup.2.sub.1] - 1)/4 and [xi] does not go to a cyclic [tau]-adic expansion, then [xi] will be a [tau]-adic expansions of length at most 8.

Our discussions and results above can be naturally generalized to the curves of genus g [greater than or equal to] 3, though it will be a bit more burdensome for high genus. In general, there exist fixed integers [k.sub.i] and [l.sub.i] non-related to q such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

hold for i = 0, 1, ..., 2g - 1. And, every element [xi] [member of] Z[[tau]] can be represented as a [tau]-adic expansion of length at most 2g + 4 as long as the related characteristic polynomial P(T) will not lead to cyclic [tau]-adic expansions.

5 Cyclic [tau]-adic expansions in Z[[tau]]

Let q = 9. Then, [a.sub.1] = [M.sub.1] - 9 - 1 [less than or equal to] 9, 6[a.sub.1] - 18 < [a.sub.2] [less than or equal to] [a.sup.2.sbu.1]/4 + 18. If [a.sub.1] = 9, then [a.sub.2] = 37 or 38, and hence, P(T) = [T.sup.4] + 9[T.sup.3] + 37[T.sup.2] + 81T + 81 or P(T) = [T.sup.4] + 9[T.sup.3] + 38[T.sup.2] + 81T + 81. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which implies that 81 can only be expressed in a cyclic [tau]-adic expansion, that is, both P(T) = [T.sup.4] + 9[T.sup.3] + 37[T.sup.2] + 81T + 81 and P(T) = [T.sup.4] + 9[T.sup.3] + 38[T.sup.2] + 81T + 81 lead to cyclic [tau]-adic expansions.

If [a.sub.1] = 8, then 31 [less than or equal to] [a.sub.2] [less than or equal to] 33. If [a.sub.2] = 32, 33, then [xi] has a [tau]-adic expansion of length at most 8. If [a.sub.2] = 31, then we can only get a cyclic [tau]-adic expansion for [xi] = 81. Thus, for the curves with the characteristic polynomial P(T) = [T.sup.4] [+ or -] 8[T.sup.3] + 31[T.sup.2] [+ or -] 72T + 81, we can not get a finite [tau]-adic expansion for 81 with the coefficients in {- [??][q.sup.2]/2[??] + 1, ..., [??][q.sup.2]/2[??]}. But if we add [+ or -] 41 to the coefficient set, then 81 will have a [tau]-adic expansion of length five.

Theorem 3 Let C is a hyperelliptic curve of genus g over [F.sub.q] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be its characteristic polynomial with a root [tau]. If there exists [xi] [member of] Z[[tau]] such that [xi] can only be expressed in a cyclic [tau]-adic expansion, then we call that P(T) leads to cyclic [tau]-adic expansions.

Let [??] be a quadratic twist of the hyperelliptic curve C and its characteristic polynomial [??](T) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with a root of [??]. Then,

1) P(T) leads to cyclic [tau]-adic expansions if and only if the following inequality (16) holds.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (16)

2) There exists an element [xi] [member of] Z[[tau]] which has only a cyclic [tau]-adic expansion if and only if there exists an element [??] [member of] Z[[??]] which has only a cyclic [??]-adic expansion, that is, P(T) leads to cyclic [tau]-adic expansions if and only if [??](T) leads to cyclic [??]- expansion.

Proof 1). Suppose [xi] can only be expressed as a cyclic [tau]-adic expansion and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Suppose [xi] can be expressed as the following cyclic [tau]-adic expansion and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (17)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)

From the equations (17) and (18) we deduce that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

Similarly, we can easily show that Inequality (19) also holds if [xi] has a longer period expression.

On the other hand, we suppose [sharp][J.sub.C]([F.sub.q]) [less than or equal to] [??][q.sup.2]/2[??] (similar discussion for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, we have

[xi] = [x.sub.0] + [x.sub.1][tau] + [x.sub.2][[tau].sup.2] + [x.sub.3][[tau].sup.3]

= #[J.sub.C]([F.sub.q]) + [tau]([x.sub.0] + [x.sub.1][tau] + [x.sub.2][[tau].sup.2] + [x.sub.3][[tau].sup.3])

2). Suppose

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a cyclic [tau]-adic expansion, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is is a cyclic [??]-adic expansion.

Similar discussions will show that Theorem 3 still holds for the hyperelliptic curve of genus g > 2.

For example, The curves with P(T) = [T.sup.4] [+ or -] 9[T.sup.3] + 38[T.sup.2] [+ or -] 81T + 81, P(T) = [T.sup.4] = 5[T.sup.3] + 15[T.sup.2] - 25T + 25 or P(T) = [T.sup.6] - 7[T.sup.5] + 21[T.sup.4] - 49[T.sup.3] + 147[T.sup.2] - 343T + 343 will lead to cyclic [tau]-adic expansions. For q = 9 = 2, only the non-supersingular curves with P(T) = [T.sup.4] [+ or -] 2[T.sup.3] + 2[T.sup.2] [+ or -] 4T + 4 lead to cyclic [tau]-adic expansions. For q = 3 and 9 = 2, only the non-supersingular curves with P(T) = [T.sup.4] [+ or -] 2[T.sup.3] + 2[T.sup.2] [+ or -] 6T + 9 or [T.sup.4] [+ or -] [T.sup.3] - 2[T.sup.2] [+ or -] 3T + 9 or [T.sup.4] [+ or -] 3[T.sup.3] + 5[T.sup.2] [+ or -] 9T + 9 will lead to cyclic [tau]-adic expansions.

Based on Hasse-Weil Theorem, that is, [([square root of q] - 1).sup.2g] [less than or equal to] #[J.sub.C]([F.sub.q]) [less than or equal to] [([square root of q] + 1).sup.2g], if q is an integer such that [([square root of q] + 1).sup.2g] [greater than or equal to] [q.sup.g]/2, then, the corresponding hyperelliptic curves will not lead to cyclic expansion. For g = 2, 3 and 4, we have q [greater than or equal to] 37, 83 and 139, respectively.

If the curve C with P(T) leads to cyclic expansion, then by Theorem 3, P(1) [less than or equal to] [??][q.sup.g]/2[??] or P(-1) [less than or equal to] [??][q.sup.g]/2[??], hence we can add [+ or -] (P(1) - [q.sup.g]) or [+ or -] (P(-1) - [q.sup.g]) to the coefficient set to make the expansion finite. For example, if the coefficient set is {0, [+ or -] 1, ..., [+ or -] 39, [+ or -] 40} [union]{ [+ or -]51}, then for the hyperelliptic curves with P(T) = [T.sup.4] [+ or -] 9[T.sup.3] + 38[T.sup.2] [+ or -] 81T + 81, all [tau]-adic expansions are finite.

6 Optimizing the length of the [tau]-expansion

Let [beta] = [b.sub.0] + [b.sub.1][tau] + ... + [b.sub.2g-1] [[tau].sup.2g-1] [member of] Z[[tau]], then since P(T) is irreducible, P(T) and B(T) = [b.sub.0] + ... + [b.sub.2g-1] [T.sup.2g-1] are coprime. Hence, there exist polynomials U(T), V(T) [member of] Z[T] such that

U(T)B(T) + V(T)P(T) = 1.

Replace T with [tau], we have [[beta].sup.-1] = U([tau]) [member of] Z[[tau]]. That is, we can use the extended Euclidean algorithm to compute the inverse of any element of Z[[tau]].

For any divisor D [member of] J([F.sub.q]n), we have [[phi].sup.n](D) = D. Furthermore, by Lemma 1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If for some D [member of] J(][F.sub.q]n), [phi](D) = D, that is, (1 - [tau]) D = < 1, 0 >, then [[PI].sup.2g.sub.i=1](1 - [[tau].sub.i])D = < 1, 0 >, that is, #J([F.sub.q])D = < 1, 0 >. For practical cryptosystems, the divisor D should be chosen to be of large order. Hence, #J([F.sub.q])D = < 1, 0 > generally does not hold. Thus, for a large multiplier m, we can obtain the divisor multiplication mD by computing [bar.m]D with [bar.m] = m mod ([[tau].sup.n] - 1) or m rood ([[tau].sup.n] - 1/[tau] - 1).

Similar to Theorem 3.1 in (8), we have the following Lemma 5.

Lemma 5 For any positive integers n and m, there exists [bar.m] [member of] Z[[tau]], such that

1. [bar.m] = mod ([[tau].sup.n] - 1),

2. N([bar.m]) [less than or equal to] [square root of g]([q.sup.g] - 1)([square root of [q.sup.n] + 1)/2([square root of q] - 1).

We can prove this lemma by letting s = m/([[tau].sup.n] - 1) = [2g - 1.summation over (i=0)] [s.sub.i][[tau].sup.i] [member of][[tau]], r = [2g - 1.summation over (i=0)] [??][s.sub.i] + 1/2[??][[tau].sup.i] and [bar.m] = m-r([[tau].sup.n] - 1).

By letting [alpha] = m([tau] - 1)/([tau] - 1) = [2g - 1.summation over (i=0)] [[alpha].sub.i][[tau].sup.i] [member of] Q[[tau]], [gamma] = [2g - 1.summation over (i=0)] [??][[alpha].sub.i] + 1/2[??][[tau].sup.i] [member of] Z[[tau]] and [bar.m] = m [gamma]([[tau].sup.n] - 1)/([tau] - 1),

we can prove the following Lemma 6.

Lemma 6 For any positive integers n and m, there exists [bar.m] [member of] Z[[tau]], such that

1. [bar.m] = m mod (([[tau].sup.n] - 1)/([tau] - 1)),

2. 2. N([bar.m]) [less than or equal to] [square root of g]([q.sup.g] - 1)([square root of [q.sup.n] - 1)/2[([square root of q] - 1).sup.2].

Thus, by Theorem 1, Theorem 2, Lemma 5 and Lemma 6, we obtain the following Theorem 4.

Theorem 4 Let C be a hyperelliptic curve of genus 9 over [F.sub.q], and let r be a root of C's irreducible characteristic polynomial P(T). If C does not lead to cyclic [tau]-adic expansions, then for a large positive integer m, m is congruent, modulo [[tau].sup.n] - 1 or [[tau].sup.n] - 1)/([tau] - 1), to a [tau]-adic expansion of length at most n+49+5 or n+4g+4, respectively. If C leads to cyclic [tau]-adic expansions, then this conclusion still holds if P(-1) - [q.sup.g] or P(1) - [q.sup.g] is added to the coefficient set.

7 An efficient scalar multiplication algorithm

According to the above discussion, we can obtain an efficient scalar multiplication algorithm. This algorithm is composed of the four steps: pre-computing, reducing the multiplier, converting the reduced multiplier into Frobenius expansion and computing scalar multiplications.

Let [a.sub.0] = 1, P[i] = [a.sub.i][q.sup.g-i] and P[g + i] = [a.sub.g-i] for i = 1, ..., g.

Algorithm 1 Compute scalar multiplication by [tau]-adic Expansion

Input: a large positive integer multiplier m and a divisor D [member of] J([F.sub.q]n).

Output: mD.

I) Pre-computing

1. For 0 < r [less than or equal to] [??][q.sup.g]/2[??], compute r D by (signed) binary method and store it as [D.sub.r].

2. For - [??][q.sup.g]/2[??] + 1 [less than or equal to] r < 0, set

rD := < x((-r)D), -y((-r)D) - h(u) >

and store it as [D.sub.r], where x((-r)D) and y((r)D) denote the first polynomial and the second polynomial of the divisor (-r)D, respectively.

II), Computing m mod ([[tau].sup.n] - 1) :

1. Find integers s[i] such that

s = [2g - 1.summation over (i=0)] s[i][[tau].sup.i] = [[tau].sup.n] - 1:

1) Initialize s[i] := -P[i] for 0 [less than or equal to] i [less than or equal to] 2g - 1.

2) For k from 1 to n - 2g, do

(a) [DELTA] := s[2g - 1].

(b) For i from 1 to 2g - 1, set

s[i] := s[i - 1] - P[i][DELTA], and s[0] := -P[0][DELTA].

3) Set s[0] := s[0] - 1.

4) Set s := [2g - 1.summation over (i=0)] s[i][[tau].sup.i].

2. Applying Extended Euclidean Algorithm, there exist t, u [member of] Z[[tau]] with [deg.sub.[tau]] [less than or equal to] 2q - 1, such that

t x s + u x P([tau]) = 1.

3. For t := [[summation].sup.2g - 1.sub.i=0] [t.sub.i][[tau].sup.i], set

[alpha] [2g - 1.summation over (i=0)] [??]m x [t.sub.i] + 1/2[??][[tau].sup.i].

4. Set [bar.m] := m - s[alpha] rood P([tau]).

III) Supposing m = [[summation].sup.2g-1.sub.i=0] [[bar.m].sub.i][[tau].sup.i] and converting [bar.m] into a [tau]-adic expansion:

1. j := 0; k := 0.

2. If [bar.m] [not equal to] 0, then do

(a) Select

[r.sub.j] [member of] {-[??][q.sup.g]/2[??] + 1, ..., -1,0,1, ..., [??][q.sup.g]/2[??]}

such that [q.sup.g]|([[bar.m].sub.0] - [r.sub.j]).

(b) Set d := ([[bar.m].sub.0] - [r.sub.j])/[q.sup.g].

(c) Set [bar.m] := [2g - 2.summation over (i=0)] ([[bar.m].sub.i+1] - P[i + 1]d)[[tau].sup.i] - d[[tau].sup.2g -1].

(d) Set j := j + 1 and k := k + 1, and go back.

IV) Computing [bar.m]D :

1. Initialize [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2. For i from k - 2 downto 0 do

(a) Set B := [phi](B).

(b) Set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

V) Output B as mD.

Since the multiplier m can also be reduced by modulo ([[tau].sup.n] - 1)/([tau] - 1), Steps I in Step II) can be replaced by the following steps:

Step II*) Computing m rood ([[tau].sup.n] - 1)/([tau] - 1):

1. Find integers s[i] such that

s = [2g - 1.summation over (i=0)] s[i][[tau].sup.i] = ([[tau].sup.n] - 1)/([tau] - 1):

1) Initialize 0 [less than or equal to] i [less than or equal to] 2.q - 1, set s[i] := 1- P[i] and t[i] :=-P[i];

2) For k from 1 to n - 2g - 1 do

(a) Set [DELTA] := t[2g - 1] and t[0] := - P[0][DELTA];

(b) For i from 1 to 2g - 1, set t[i] := t[i - 1] - P[i][DELTA] and s[i] := s[i] + t[i];

3) Set s := [2g - 1.summation over (i=0)] s[i][[tau].sup.i];

Note that if P(1) [less than or equal to] [??][q.sup.g]/2[??] or P(-1) [less than or equal to] [??][q.sup.g]/2], then add P(1) - [q.sup.g] or P(-1) - [q.sup.g] to the coefficient set. Take P(1) < [q.sup.g]/2 for example, we only make some minor modifications in Algorithm 1 as follows:

First, add the computation of [+ or -] ([q.sup.g] - P(1))D in the precomputation step; Second, change the step (a)-(b) in Step III) as follows:

(a*) If [absolute value of [[bar.m].sub.0] [less than or equal to] [??][q.sup.g]/2[??] [[bar.m].sub.0] = P(1) - [q.sup.g], then set [r.sub.j] := [[bar.m].sub.0],

otherwise, go to the next step:

(b*) Select

[r.sub.j] [member of] {P(1) - [q.sup.g], - [[q.sup.g]/2] + l, ..., -1,0,1, ..., [??][q.sup.g]/2[??]} such that [q.sup.g]|([[bar.m].sub.0] - [r.sub.j]).

We implement Step II)-III) in Algorithm 1 in Maple for five hyperelliptic curves and get the Table 1. Table 1 lists five hyper-elliptic curves and the bits of the orders of their corresponding Jacobian groups, the average lengths and densities of the [tau]-adic expansions of the multipliers approximate to the Jacobian group orders, and the average lengths (1)-(2) and densities (1)-(2) of the [tau]-adic expansions of the multipliers after reduced by modulo ([[tau].sup.n] - 1)/([tau] - 1) or ([[tau].sup.n] - 1), respectively. The density means the ratio of the number of the non-zero coefficients to the length in a [tau]-adic expansion.

The corresponding characteristic polynomials of the five hyperelliptic curves in Table 1 are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively.

Table l shows that, when the multipliers are reduced by modulo ([[tau].sup.n] - 1)/([tau] - 1) or [[tau].sup.n] - 1, the average lengths of the [tau]-adic expansions are between n - 2 and n + g, or between n + 1 and n + 9 + 1, respectively. It also shows that, if the multipliers are not reduced, then the average length of [tau]-adic expansions is about [q.sup.q] times of the extension degree of the field. While their average densities are almost the same whether the multipliers are reduced or not.

Suppose the multiplier m ~ [q.sup.gn] (near to the Jacobian order). Then, to compute mD, the binary method needs on average ng/3 [log.sub.2] q divisor additions and ng [log.sub.2] q divisor doublings. While according to our experiments, Algorithm 1 needs on average n + g/2 divisor additions and g [log.sub.2] q - 1 divisor doublings, plus about n + g/2 divisor evaluations of Frobenius endomorphism. If we implement Algorithm 1 in some normal basis, then the Frobenius evaluation cost can be considered free. Hence, according to Theorem 14 in (11), Algorithm 1 will cost about 55% less than the signed binary method for the curves listed in Table 1. It follows that our algorithm will greatly speed up the implementation of hyperelliptic curve cryptosystems since the divisor scalar multiplication is the most time-consuming operation.

8 Conclusion

In this paper, we have applied Frobenius endomorphism and Euclidean length to reduce the multipliers in divisor scalar multiplications by modulo [[tau].sup.n] - 1 or ([[tau].sup.n] - 1)/([tau] - 1), and show that the upper bound of the lengths of the reduced multipliers' [tau]-adic expansions is n + 4g + 5. In addition, our experiment results show that the lengths of the multipliers' [tau]-adic expansions are actually between n - 2 and n + g + 1. While Gunther et al(8) did experimentally show that the two hyperelliptic curves [v.sup.2] + uv = [u.sup.5] + [alpha][u.sup.2] + 1 ([alpha] = 0, 1) have some [tau]-adic expansions of length about n + 4/3 (which are near to our experimental result, but they did not give a theoretical proof.

In practical hyperelliptic curve cryptosystems, since the parameters q, g, n and the basic divisor D are relatively fixed, we can pre-compute [[phi].sup.i]([r.sub.j]D) for 1 [less than or equal to] i [less than or equal to] n + 4g+ 4 and -[??][q.sup.g]/2[??] + 1 [less than or equal to] j [less than or equal to] [??][q.sup.g]/2[??] and then store the results as a table. If we employ this table, then our algorithm only needs at most n + 4g + 4 divisor additions, which is approximately one third computation expense that the binary method does. In addition, based on the Proposition 3.4 in (12), the elliptic curve rational point group [E.sub.c]([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is isomorphic to the Jacobian group [J.sub.c] ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) under their group law definitions when the curve C's genus g = 1, hence, our Algorithm 1 is also applicable to the scalar multiplication computations on [E.sub.c]([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]).

Acknowledgement

This research is supported by the National Science Foundation of China (No.60763009), the science and technology Key Project of the Ministry of Education of China(No.207089), and Zhejiang Natural Science Foundation of Outstanding Youth Team Project(No.R1090138).

References

[1] N. Koblitz(1989). A Family of Jacobians suitable for discrete log cryptosystems, Advances in Cryptology-Crypto'88, LNCS 403, Springer-Verlag, pp.94-99.

[2] N. Koblitz(1989). Hyperelliptic cryptosystems, Journal of Cryptology, No. 1, pp. 139-150.

[3] J. Pollard(1978). Monte Carlo methods for index computation mod p, Mathematics of Computation, No.32, pp. 9181C924.

[4] S. C. Pohlig, M. E. Hellman(1978). An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Information Theory, IT24(1), pp.1061C110.

[5] A. Weil(1949). Number of solutions of equations in finite fields. Bull. AMS. 55, pp.497-508.

[6] V. Muller(1998). Fast multiplication on Elliptic Curve over Small fields of Characteristic Two. Journal of Cryptology. 11, pp. 219-234.

[7] N. P. Smart(1999). Elliptic Curve Cryptosystems over Small Fields of Odd Characteristic. Journal of Cryptology. 12, pp.141-151.

[8] Ch. Gunther, T. Lange and A.Stein(2001). Speeding Up the Arithmetic on Koblotz Curves of Genus Two. LNCS 2012,pp. 106-117.

[9] K. Matsuo, J.Chao, S.Tsujii(2002). An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields. LNCS. 2369, pp. 461-474.

[10] D. Maisner, E. Nart(2002). Abelian surfaces over finite fields as Jacobians. Experimental Mathematics. 11, pp. 321-337.

[11] A. Enge(2001). The Extended Euclidean Algorithm on Polynomials. and the Com-putational Efficiency of Hyperelliptic Cryptosystems, Design, Codes and Cryptography. 23(1), pp.53-74.

[12] J. H. Silverman(1986). The Arithmetic of Elliptic Curves, Spriger-Verlag, pp.66-67.

Lin You

School of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China

mryoulin@gmail.com

Jiwen Zeng

Department of Mathematics, Xiamen University, Xiamen 361005, China

jwzeng@xmu.edu.cn
```Figure 1: Average Lengths and Densities of [tau]-adic Expansions

bits
of    average   average
Hyperelliptic curves        q    n    orders    length    density

[v.sub.2] + ([u.sup.2] +    2    61       122   242.125     0.749
u + 1) v = [u.sup.5] +           67       134   264.250     0.738
[u.sup.4] + [u.sup.3] + u       273       146   291.000     0.758
89       178   355.000     0.736
113       226   451.000     0.741

[v.sub.2] = ([u.sup.5] +    3    61       194   244.000     0.832
[u.sup.4] - [u.sup.3] +          67       213   267.500     0.828
[u.sup.2] - u + 2               397       308   386.833     0.844
103       327   412.333     0.826
113       359   452.000     0.824

[v.sub.2] + v               2    29        87   168.400     0.828
[u.sup.7] + [u.sup.6]            37      1ll    210.000     0.861
[u.sup.5]                       243       129   254.000     0.867
59       177   352.000     0.845
67       201   398.000     0.865

[v.sub.2] = ([u.sup.5] +    5    61       284   246.000     0.906
[u.sup.4] + 2[u.sup.3] +         67       312   270.000     0.916
[u.sup.2] + u + 2               571       330   285.600     0.936
79       367   318.000     0.936
83       386   334.000     0.930

[v.sub.2] + ([u.sup.7] +    5    29       203   174.000     0.986
[u.sup.5] + [u.sup.3] +          31       216   186.000     0.985
u - 1                           537       258   222.000     0.998
43       300   258.000     0.979
53       370   318.000     0.991

reduced   reduced
average   average
length    density
Hyperelliptic curves        q    n       (1)       (1)

[v.sub.2] + ([u.sup.2] +    2    61    62.000     0.761
u + 1) v = [u.sup.5] +           67    64.667     0.732
[u.sup.4] + [u.sup.3] + u       273    70.500     0.756
89    87.833     0.784
113   110.667     0.768

[v.sub.2] = ([u.sup.5] +    3    61    61.833     0.865
[u.sup.4] - [u.sup.3] +          67    67.667     0.872
[u.sup.2] - u + 2               397    97.667     0.887
103   104.500     0.890
113   112.667     0.873

[v.sub.2] + v               2    29    30.333     0.890
[u.sup.7] + [u.sup.6]            37    37.667     0.858
[u.sup.5]                       243    42.833     0.883
59    60.500     0.859
67    67.167     0.868

[v.sub.2] = ([u.sup.5] +    5    61    62.167     0.949
[u.sup.4] + 2[u.sup.3] +         67    68.667     0.973
[u.sup.2] + u + 2               571    72.167     0.972
79    81.167     0.955
83    84.500     0.955

[v.sub.2] + ([u.sup.7] +    5    29    31.667     0.984
[u.sup.5] + [u.sup.3] +          31    33.667     0.980
u - 1                           537    40.833     0.988
43    44.167     0.985
53    55.167     0.988

reduced   reduced
average   average
length    density
Hyperelliptic curves        q    n       (2)       (2)

[v.sub.2] + ([u.sup.2] +    2    61    62.833     0.756
u + 1) v = [u.sup.5] +           67    68.000     0.733
[u.sup.4] + [u.sup.3] + u       273    73.000     0.752
89    87.500     0.760
113   112.333     0.712

[v.sub.2] = ([u.sup.5] +    3    61    62.000     0.869
[u.sup.4] - [u.sup.3] +          67    68.167     0.905
[u.sup.2] - u + 2               397    99.500     0.901
103   105.333     0.889
113   114.667     0.903

[v.sub.2] + v               2    29    29.667     0.832
[u.sup.7] + [u.sup.6]            37    38.333     0.878
[u.sup.5]                       243    45.500     0.865
59    59.833     0.847
67    70.000     0.877

[v.sub.2] = ([u.sup.5] +    5    61    64.000     0.958
[u.sup.4] + 2[u.sup.3] +         67    70.500     0.962
[u.sup.2] + u + 2               571    74.167     0.951
79    81.667     0.943
83    85.167     0.967

[v.sub.2] + ([u.sup.7] +    5    29    33.500     0.985
[u.sup.5] + [u.sup.3] +          31    34.833     0.990
u - 1                           537    40.333     0.979
43    47.333     0.986
53    57.667     0.991
```