Informatica 34 (2010) 189-227 189 Fast Scalar Multiplications on Hyperelliptic Curve Cryptosystems 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 Keywords: Hyperelliptic Curve cryptosystems, scalar multiplications, Frobenious Endomorphism, Frobenious Expansion, Euclidean length Received: August 14, 2008 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 multiplierin a scalarmultiplica-tion can be reduced and converted into a Frobenius expansion of length approximate to the field extension degree, and then propose an efficient scalarmultiplication algorithm. Ourmethod is an extension of the results given by Müller, Smart and Günther 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. Povzetek: Predstavljena je metoda pohitrenega skalarnega množenja. 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 Fq be the finite field of q elements. A hyperelliptic curve C of genus g over Fq is defined by the equation v2 + h(u)v = f (u), (1) simultaneously satisfy the equation v2 + 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 Fq 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 Fq is defined as a finite formal sum of rational Fq -points D = J2 miPi on C with its degree defined as the integer J2 mi. The Jacobian group Jc (Fq) of the curve C over Fq is an Abelian group composed of reduced divisors on C. Every element or reduced divisor D in Jc (Fq) can be uniquely expressed by a pair of polynomials < a(u),b(u) > with the properties deg„5(u) < deg„a(u) < g b(u)2 + h(u)b(u) — f (u) = 0 mod a(u) (2) where h(u), f (u) e Fq with deg„(h) < gand deg„(f) = 2g + 1, and there is no solution (u, v) e Fq x Fq which where a(u), b(u) G Fq[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 Jc (Fq) 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 D + D + ■■■ + D for a given divisor D e J(Fq^) and a positive integer m > 1, which is denoted as mD. 228 Informatica 34 (2010) 227-236 L. You et al. 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 Fq, and also a divisor D e J(Fq~). - Alice randomly chooses an positive integer mA that is smaller than JC (Fq™), and then compute the scalar multiplication DA = mAD and send DA to Bob. - Bob similarly chooses an positive integer mB, compute Db = mB D and send DB to Alice. - Alice and Bob compute the scalar multiplications DA}B = mADB and DB}A = mBDA,respectively. Since Dab (mAmB )D = = mADB (mB mA)D = mA(mB D) D get their shared secret key DA}B. B,A, Alice and Bob 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 $ of Fq is defined as the map x i—> xq for x e Fq. Naturally, $ induces an endomorphism $J of JC (Fq^) as follows: Jc (Fqn ) g g-i J2b i=0 j=0 »I J Jc (Fqn ) j xj > < E aqx\ E jxj >, i=0 j=0 g-i - Using this shared secret key DA}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), Müller and Smart employed Frobenius automorphism to compute point scalar multiplications on elliptic curves over small fields of characteristic even or odd, respectively. In (8), Günther 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 ^(D) is much faster than doubling D, and the other is that every Z[t]-integer can be represented as Frobenius expansion or t-adic expansion of finite lengths, where t 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[t] with t a root of some hyperelliptic curve's characteristic polynomial. In Section 3, we discuss the lengths of t-adic expansions of algebraic integral numbers in Z[t] and obtain an upper bound for them. In Section 4, we study the cyclic t-adic expansions and the optimization of the t-expansions's lengths. The t-expansion's where D =< a(u), b(u) >=< aix1, bjxj > is a re- i=0 j=0 duced divisor or an element of Jc (Fq™) with at, bj e Fq™. For convenience, 4>j is also denoted by Lemma 1((5)) For any positive integer r, let Mr denote the number of rational points of the hyperelliptic curve C defined by Equation (1) over Fqr and Jc (Fqr) denotes the order of the Jacobian group Jc (Fq). Then 1. The zeta-function Z(t) has the expression Z(t) = exp(V M"tn) = -tgl- , u "=i n (! - t)(! - qt) where L(t) is an integral coefficient polynomial of degree 2g. L(t) 2. Let 2g P(T) = t2gL(1/T) = n(T - Ti), then \Ti\ = ^fq, and the roots come in complex conjugate pairs such that there exists an ordering with Ti+g = fi, and hence, Ti+g Ti = q. 3. P(T) is the characteristic polynomial of Frobenius endomorphism 0 and P (T) is an integral coefficient polynomial of the following form P (T ) = T2g + aiT2g-i + a2T2g-2 + ■■■ + I a g Tg + qag-iTg-i + ■■■ + qg-iaiT + qg ' 4. Let a0 = 1, then for 1 < i < g iai = (Mi - qi - 1)ao + (M-i - qi-i - 1)ai + ■■■ + (Mi - q - 1)ai-i (3) 5. For any positive integer n, 2g JC (Fqn ) = JJ(1 - Ti"). FAST SCALAR MULTIPLICATIONS. Informatica 34 (2010) 227-236 229 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 (F?™) have a large prime integer factor, or to the best, JJc (Fq™) 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[t] Let C be a hyperelliptic curve of genus g over Fq with the characteristic polynomial (3). Let t be a root of P(T). Then, since P(T) is irreducible, every element £ in Z[t] can be uniquely expressed as the form i i i 2g-1 Xo + XiT +----+ X2g-iT . Let t = t1 , t2, • • •, Tg be the g roots of P(T) which are not conjugate each other. Then, we can define a positive number N (£) corresponding to £ as the following N (0 = 2g-1 2g-1 iE xiTii2 + ••• + iE xtrg |2, where \x\ denotes the complex absolute value of x. N(£) is often called the Euclidean length of £. It is clear that N (£n) < N (£)N (n) and N(£ + n) < N(£) + N(n) hold for any £, n € Z[r]. And N(£)2 is a positive definite quadratic form in the variables xo, xi, • • •, x2s_i, with the coefficients being integer polynomials of P(T)'s coefficients ai(1 < i < g). For g =1 and £ = x0 + x1t, we have N(£)2 = x2 - aixoxi + qx2. For g = 2 and £ = x0 + x2t + x2t2 + x3t3, we have N(£)2 = 2x0 - aixoxi + (a2 - 2a2)xox2 -(ai — 3(aia2 — aiq))xox3 + 2qx2 — aiqxix2 . , n . r)r) r\ n n + (ai - 2a2)qxix3 + 2q x2 - aiq x2x3 + 2q x3 In general, let Si = E^UT + tj), X = (xo ,x1, ••• , x29_2), and let A = I 3 Si/2 S2/2 Si/2 qg qSi/2 S2/2 qSi/2 S2-1/2 \ qS2g-2/2 q2S2g-3/2 \ S2g-l/2 qS2g-2/2 q2S2g -3/2 Then we can easily prove N (£)2 = XAXT, where Si can be computed by the following Newton's formula: Si + aiSi-1 + a2Si-2 +----+ ai-iSi + iai = 0 with a0 = 1 and aj = a2g-jqj-g for j > g. 4 Convert m into t-adic expansion Similar to Lemma 1 in (6), we have Lemma 2 (Division With Remainder in Z[t]) Let m e Z[t], then there exists a unique pair of elements m' and r such that m = mT + r (4) with m' e Z[t], r e {-\qg/2] +1, • • • , [qg/2\}. Theorem 1 Let m e Z[t], then m can be uniquely represented as a t-adic expansion k-1 m = E rT + m'T k, n e {-\qg/21 + 1 ••• , W/2\}- i=0 If k > 2 logq , then N(m') < ^^. Proof Iterate the Division With Remainder in Z[t] for m0 = m, then we have mi = mi+iT + ri, n e {—Tqg/2] + 1, • • • , [qg/2\}. Hence, j-i m0 = ^^ riTi + mj t j. i=0 Apply triangle inequality for Euclidean length in mi = mi+iT + ri, and we will get N (mj) < NVj + VW/2\) vqj vq -1 Hence, if < N(™o) ^ Vs ,/qi — 2(v/q-1) j > 2 log, 2(^q - 1)N(mo) V9 ' then N (mj ) < Vg0qV2j+i/2) _ qg^g Vq - 1 2(jq - 1)' 2(/q-1)N gq /g Hence, for k = [2logq 2^v/q i^)N(m) 1 + 1 and m' = mk, we □ have N(m') < 2/—-). Lemma 3 a1 — 2[2yq], And if a2 = 0, then |a1| < ,/q. Proof ai < holds obviously since every root of P(T) has the complex absolute value ,Jq. If a2 = 0, then |ai| < ^/q follows the facts M2 - q2 - 1 + a2 = 0 and M2 > 1. Lemma 4 If C is a hyperelliptic curve of genus 2 with the irreducible characteristic polynomial P(T) = T4 + aiT3 + a2T2 + aiqT + q2, then ai — 4a2 + 8q is non-square and 2|ai|Vq — 2q 3, then £ has a t-adic expansion of length l < 2g+4. Proof Suppose £ e Z[t] satisfying the inequality (5), then N(02 < 9q 2g 4(yq -1)2' which implies \x1\ < 2. If x1 = 0, then £ = (x0 ± 4) + (x2 ± a2)T2 + x3T3 ± t4 (if \x2 ± a2\ < 2) or £ = (xo ± 4) + (x2 ± a2 ± 4)t2 + x3T3 + (±1 ± a2)T4 ± t6( if \x2 ± a2\ = 3) is a t-adic expansion of length 5. If 0 < \x1 \ < 2 and x3 = 0, then £ is itself a t-adic expansion or £ = (xo ± 4) + xiT + (x2 ± a2 ± 4)t2 + (±1 ± a2)T4 ± t6 is a t-adic expansion of length l < 5. If 0 < \x1\ < 2 and \x3\ = 1, then from the equation (8) we obtain \x2\ < 1. Hence, £ = (x0 ± 4) + x1t + (x2 ± a2)T2 + x3t3 ± t4 is a t-adic expansion of length l < 5. If \x0\ = 4, then from (6), we have \x2\ < ^26/(V2-1)2-1Bx16 + 4/8 < 2, and so \ x2 ± a2\ < 2. Hence, £ is a t-adic expansion of length l < 4. d) If q = 3, then \a2 \ < 3. From (7), we have \ x0 \ < 7, \ x1 \ < 4, \x2 \ < 2 and \x3 \ < 1. If \x0 \ < 4, then £ is itself a t-adic expansion of length 4. If \x0 \ > 5 and \a2\ = 3, then 1. Since q2 + t4 = 0 or q2 = -t4, it obviously follows that from (6) we have 3x2 + (6x2 ± x0)2 + 9x2 + 3(6x3 ± x1 )2 < m has a t-adic expansion of length about 2 |_l°gq m\. 2. Suppose a1 = 0. Then \a2 \ < 2q, and it follows 4q2 — a2 > 4q — 1. Hence, N (£)2 = 2(x0 — a2X0X2 + qxi — a2qxx + q2x2 + q3x3) = 2((x0 — a2/2x2 )2 + (q2 — a2/4)x2 + q(xi — a2/2x3)2 +q(q2 — a2/4)x2) 34/(V3 — 1)2, which implies x1 =0 or x3 = 0. Thus, £ = x0 + x1T + x2t2 + x3t3 = (x0 — 9)+ x1T + (x2 — a2)T2 + x3T3 — T4 or £ = (x0 — 9)+x1T + (x2 — a2 ± 9)t2 +x3T3 + (1±a2)T4 ±t6 is a t-adic expansion of length l < 5. 3. Suppose a2 = 0. Then by Lemma 3, \a1\ =1 for q = 2, 3 and \ a1 \ < ^Jq for q > 3. Since N(Ç)2 = 2^0 - «1x0x1 + «1x0x2 - («3 + 3a1q)x0X3 y2 _ n* nrf-, ^^ _L n2 „ _L O^^2 = 2((1 - ^)x20 + q2(x2 - 222x0)2 + (q - %)*1 +q3(x3 - xi)2) < q4 .. < 2(v5-i)2 2q2 )~ 2 4q ) +2qx1 — aiqxix2 + a1qxix3 + 2q2x2 +2q3x3 — aiq2x2x3 = qq-a0r x2 + 2q(xi + ai x3 — ^ xo — at x2)2 Thus, \ 1 - 4q2 \i/2 \xo \ \ 1 - 4=22 \i/2 \xi \ \ q2 - a2/4 \i/2 \x2 \ \ q2 - a2/4 \i/2 \x3 \ < < < < 2^v/q-i) q2 2(q-Vq) q2 2(vq-i) q2 2(q-Vq) (6) (7) + + ( q(i6q2 1 (x3 + q(i6q2 af) i2ai q xo — 4q+af x2)2 (9) q(at-4q) 4 < 2^v/q-i)2 it follows that (ai — q) „2 x0 + x22 < q(a\ — 4q) ^ ai + 4q 2 2(^9 — 1)2(8q + a2) xi < ' \ x3 \ < 7^- and so, x0 < \x2 \ < ^V?-1W4?-^ I'"31 ^ (q-Vq)V4q-1- a) If q > 4, then \x0\ < q2 and \x1 \ < q2/2. Hence, if x0 > q2/2(similar for x0 < —q2/2), then from (6), we have (2q2x2 — a2x0)2 < q6/(yq — 1)2 — q4(4q —1)/4, and so \ x2 — a2i < \ x2 — a* x0 \ + \J2! x0 — a2 \ 4 and \ x0 \ < q2/2,then £ isitselfa T-adic expansion of length 4 . c) If q = 2, then a2 = ±1. Hence, from (7), we have \ x0 \ < 4, \x1 \ < 3, \ x2 \ < 2 and \ x3 \ < 1. If \ x0 \ < 2 and \ x1 < 2, then and |xo| < M < •/qq' i+ q-af i+ 3q V2(-q-i^8q+af V2(-q-i) 1 2-yq-1 4(\/q-i) 4q < VBq 8q+af 3V2(-q-i) (10) (11) Similarly, we will get |xi| < |x3| < V2(q--q) 1 4q V2(-q-i)^8q+aiy q-at VBq2 3V2(q--q) q, A+ 2./q-l (12) 4(q- \/q) If q > 4 then \xi\ < q2/2 for i = 0, 1, 2, 3. Hence, £ is a t-adic expansion of length at most 4. Let q = 3, then from (9), (10),(11) and (12), we have \ x0 \ < 7, \x1\ < 3, \x2\ < 1 and \x3\ < 1. Without loss of generality, 3a a at 8 a a x o 2 2 4 q q 2 2 q < FAST SCALAR MULTIPLICATIONS. Informatica 34 (2010) 227-236 231 suppose ai = 1 and x0 > 0, then Ç = xo + xit + X2T2 + X3t3(if |xo| < 4) = (X0 - 9) + (Xi - 3)T + X2T2 + (X3 - 1)t3 - t4 (if |x0| > 4 and |x1 - 3| < 4) = (xo - 9) + (xi - 3 + 9)t + (X2 + 3)t2 + (X3 - 1)t3 + t5 ( if |x0| > 4 and x1 - 3 < -4) is a t-adic expansion of length at most 5. Similar discussion will show that £ can also be represented as a t-adic expansion of length at most 5 for q = 2. 4. Suppose a1 =0 and a2 = 0. Then for £ = x0 + x1t + x2t2 + x3t3, we have N («) o 3 / a 1 I a?—2a2 ai(ai — 3a.2 + 3q) >2 2g (x3 - 41 X2 + 4q2 X1 - -^-X0) , q(16q — aj)( , a!(a11—2a2 — 4q) — _* + 3_Z_2 + + q (x2 + /I« 2\ X1 + ' 0 v q(16 q — a1) — a1 + 6a2 _f—4q^^—0__f+3fqf. + 16q — a I (X1- ai(16q2 — 14qa1 —2a1 + 13a1a2 —20a2+32qa2) q2(16q—a1) Lxo )2 2q( —a1 + 6a1 a2—4qa1—8a2+32 q2 ) xo)2 1 a1 a2—5qa1a2 + 7q2a1+a3 + 2qa2 — 4q2a2 — 8q3 q2(a1—2a2—4q) 21 __L~ I a1—2a2^ a1 ^ ^2 4 + --2q2(x2 - ^ X3 + ^ + q2(16q — a1) 4q x0 - (x3 + 4q X1)2 — 3a1 + 10a1a2 — 12a1q q2(16q —a1) x0 + (4a2 —8q — a1)(a4 — 3a1a2 + 3a2q — 2 a 2 q —4q2) q2(16q —a1) 3a1 — 8a2 q(16q — a1) X1)2 (x0+ a1q(14a1q + 2a4 —32a2q —13a1a2 —16q2 + 20a2) + < _^_ ^ 2(^q— 1)2 Let 2(4a2 — oq — a 1 )( a 1— 3 a 1 a2 qa4 — J a1 a2 — 5qa1a2 + 7q2a1+a2 + 2qa2 —4q2a2 — 8q3 2 _4_3_2_~ + 3 a 2 q — 2a~q— 4q2 X1 (13) we will get \x2\ < 2(q—qfaWG/F and |x31 < ^O2q „ Vh/f . That is, \xo\ < \xi\ < \x2\ < \x3\ < -}vhtf V2q3 2(-q-1) _ 2(Jqq-i)VWF 2&VÖJF- -2q2 (14) without loss of generality, suppose ai > 2. Because both H/F and G/F are strictly increasing functions of a1 except in a neighborhood of a1 = 4^/q — 2, they will reach their possible maximal values at a1 = 2(2^fq — e) — 2 since a1 < 2\2y^J and a1 is even, where e = 2^/q — \2y^J. Replace a1 and a2 in H/F with 2(2^Jq — e) — 2 and 2q + a1/4 — 1, respectively. Then, since e = 2^q - [2^q\ > 2L2v/qJ+i ^ 579 > suq,weget H/F = -2(-4Vq£-4Vq+£2 + 2£ + 2)_ n!r £(4£+£3+4£2-8yq£2-24^q£-16yq+16q£ + 32q) ~ 1 < 1 < 5 ~ 4^qs < 4^q • 3 < 12 • Similarly, we have G/F « < • < ^. ii) Let q be square and a2 = —2q + 2|a1|y/q + 1. Without loss of generality, suppose a1 > 1. Since a2 < a1/4 + 2q, it follows a1 < 4^Jq — 3. It is easy to show that H/F is strictly increasing for 1 < a1 < 4^/q — 3. Hence, H/F will reach its maximal value at a1 = 4^q — 3, and so, H/F < 4q-1/2. Similar discussion will induce G/F < 27q1/2. iii) Let a2 = —2q + 2|a1|vq + S with S = [2|a1^v/q] — 2|a1|vq (q is non-square). Still suppose a1 > 1 . Then, a1 < 4^q — 2 VS. Let a1 = 4^/q — 2 + e , where 0 < e < 1 such that a1 is an integer, that is, a1 = \4yfq — 2]. Replace a1 and a2 in H/F with 4^Jq — 2 + e and —2q + 2a1^fq + S, respectively. Then, since S = |~2a1vq] — 2a1^fq > ^^q, we have H/F « —4q1/2 = Wyq < 2 • Similar discussion will induce G/F « | ^qS-1 < 18q • From all the discussion above, we conclude that if a2 = 2q + (a2 — 1)/4, then F = —qa1 + 4 a2 a2 + 5qa1a2 — 7q2a1 — a3 — 2qa2 +4q2a2 + 8q3 G = —a1 + 3a2a2 — 3a2q + 2a2q + 4q2 • H = —a2 + 2a2 + 4q Since |a11 < 2\2^qJ and 2|a1|^q — 2q < a2 < a\/4 + 2q, we have F > 1, G > 0 and H > 0. Hence from (13) we get M < ^fe VHf and < 27^1)\/G/F. Similarly, H/F < 4 q-1/2 2 and ^ q1/2 5 q 18q G/F < Hence, if q is square, we have i \xo\ < I \xi\ < \X2\ < \X3\ < and if q is non-square, we have if q is square if q is non-square if q is square if q is non-square. -2- q9/4 V36 q7/4 q VU q5/4 -5 q -2-q3/4 -5 q If a2 = 2q + a2/4 or a1 = ±(2q + a2)/(2^q), then F = 0, which contradicts F > 1. While, it is very likely that H/F or G/F takes maximal values at a2 = 2q + ai/4 — d or —2q + 2|a1|^q+S, where0 = 1 or 1/4 , S = 1 or |"2|a1 |^q]—2|al|^q. According to (10), if C is a curves with a2 = 2q + (a1 — 1)/4, then it may not be a hyperelliptic curve. Thus, we do not consider this case. i) Let a2 = 2q + a2/4 — 1. Then, if a1 = ±(4y^ — 2), H/F and G/F are strictly increasing or decreasing with a1 > 0 or a1 < 0. Hence, if q is a square, then H/F and G/F reach their maximal values at a1 = ±(4Vq — 4), that is, and 2( 1872g2+8g3/2+1152g5/2 +1353q-368Vq-168) rpsnpctivp]y and 3(-160q+9+256q2) , respectively. Thus, H/F < 3q-1/2 and G/F < 3^fq. If q is non-square, \xo\ \xi\ \x2\ \x3\ < < < < 2q5/2 V3ëq2 V36q3/2 ' 2q In the following discussions, without loss of generality, we assure a1 > 0 and x0 > 0. And, for the worst case, we also assume that all xi is near to its upper bound. Then, if q is a square no less than 49 and a2 > 0(similar discussion for a2 < 0), we have £ = xo + X1T + X2T2 + X3T3 + X4T4 = (xo - doq2) + (X1 - doa1 q)T + (X2 - doa2)T2 +(x3 - doa1)T3 - dot4 = (xo - doq2) + (x1 - doa1 q + d1q2)T + (x2 - doa.2 +d1a1q)T2 + (x3 - doa1 + d1a2)T3 + (-do + d1a1)T4 +d1T 5 = (xo - doq2) + (x1 - doa1 q + d1q2)T + (x2 - doa2 +d1a1q + d2q2)T2 + (x3 - doa1 + d1a2 + d2a1 q)T3 +(-do + d1a1 + doa2)T4 + (d1 + d2a1)T5 + d2T6, 2 x 0 o + 2 232 Informatica 34 (2010) 227-236 L. You et al. which implies that £ is a t-adic expansion of length at most 7, where d0 is an integer close to —j qi/4 such that \x0 — d0q2\ < q2/2. di = 0, —1 if xi > 0, or di = 1, 2 if xi < 0. d2 =0 if di = 0,1, or d2 = 0,1 if di = —1, or d2 = —1 if di = 2. By almost the same discussions, we will show that £ can be expressed as a t-adic expansion of length at most 8 if q is a nonsquare no less than 37. If q is a square smaller than 25 or a non-square smaller than 31, then £ may go to a cyclic t-adic expansion with the coefficients in R. But, we can easily show that if a2 = 2q + (ai — 1)/4 and £ does not go to a cyclic t-adic expansion, then £ will be a t-adic expansions of length at most 8. Our discussions and results above can be naturally generalized to the curves of genus g > 3, though it will be a bit more burdensome for high genus. In general, there exist fixed integers ki and li non-related to q such that M < kiq(5g-2i-l)/4 if q is square if q is non-square (15) hold for i = 0, 1, • • •, 2g — 1. And, every element £ e Z[t] can be represented as a t-adic expansion of length at most 2g + 4 as long as the related characteristic polynomial P(T) will not lead to cyclic t-adic expansions. □ 5 Cyclic t-adic expansions in Z[t] Letq = 9. Then, ai = Mi-9-1 < 9, 6ai-18 < a2 < ai/4+ 18. If ai = 9, then a2 = 37 or 38, and hence, P(T) = T4 + 9T3+37T2 +81T+81 or P (T) = T4+9T3+38T2 +81T+81. We have 81 = -a2T2 + (a2 - 9)t3 + ((89 - a2)t4 + (a2 - 8)t5 +8t 6 + T7) = -a2T2 + (a2 - 9)t3 +—(a2 - 8)t4 -T((89 - a2)T4 + (a2 - 8)t5 + 8t6 + t7), which implies that 81 can only be expressed in a cyclic t-adic expansion, that is, both P (T ) = T4 + 9T3 + 37T2 + 81T + 81 and P (T) = T4 + 9T3 + 38T2 + 81T + 81 lead to cyclic t-adic expansions. If ai = 8, then 31 < a2 < 33. If a2 = 32, 33, then £ has a T-adic expansion of length at most 8. If a2 = 31, then we can only get a cyclic t-adic expansion for £ = 81. Thus, for the curves with the characteristic polynomial P (T) = T4 ± 8T3 + 31T2 ± 72T + 81, we can not get a finite t-adic expansion for 81 with the coefficients in {-\q2/2~\ +1, • • • , [q2/2\]. But if we add ±41 to the coefficient set, then 81 will have a t-adic expansion of length five. Theorem 3 Let C is a hyperelliptic curve of genus g over F, and P (T ) = T2g + aiT2g-i + • • • + ag Tg + • • • + aiqg-1T + qg be its characteristic polynomial with a root t. If there exists £ e Z[t] such that £ can only be expressed in a cyclic t-adic expansion, then we call that P(T) leads to cyclic t-adic expansions. Let C be a quadratic twist of the hyperelliptic curve C and its characteristic polynomial P(T) as T2g - aiT2g-i + • • • + (-1)gagTg +----aiqg-1T + qg with a root of T. Then, 1) P (T) leads to cyclic t-adic expansions if and only if the following inequality (16) holds. Pc (Fq ) <[qg/2J or Pc (F, ) < [qg/2J. (16) 2) There exists an element £ e Z[t] which has only a cyclic t-adic expansion if and only if there exists an element £ e Z[T] which has only a cyclic T-adic expansion, that is, P (T) leads to cyclic t-adic expansions if and only if P(T) leads to cyclic T-expansion. Proof 1). Suppose £ can only be expressed as a cyclic t-adic expansion and £ = xo + xi T + X2T2 + X3T3 = ro ± T(xo + XiT + X2T2 + X3T3), xo > Lq2/2J, Irol < [q2/2j. Let xo - ro = dq2, then xo = ±(xi - daiq), xi = ±(x2 -da2), x2 = ±(x3 - dai) and x3 = +d. and hence, xo = -d - dai - da2 - daiq = d(q2 - Pc (F,)) when x3 = -d, or xo = -d + dai - da2 + daiq = d(q2 - Pc (F,)) when x3 = d. It follows ro = -dJc (F, ) and dJc (F, ) < Lq2/2J, or ro = -d Pc (F, ) and dJc (f, ) < Lq2/2J. Hence Pc (F,) = |ro l/d < Lq2/2J or Pc(F,) = lrol/d Lq2/2J,Iril < Lq2/2J,i = 0,1. Let xo - ro = dq2 and xi - daiq - ri = eq2, then we have xo = x2 - da2 - eaiq, xi = x3 - dai - ea2, x2 = -d - eai and x3 = -e. Thus, xo = dq2 + ro = -d - eai - da2 - eaiq and xi = daiq + eq2 + ri = -e - dai - ea2, which implies ro + ri = -(d + e) Pc(F,). (17) Hence, if ld + el > 2, then Pc (F, ) < (lrol + lri l)/ld + el < Lq2/2J. If d + e = 0, then ro = -d P^ (F,), and so, Pc (F,) < lrol/d < Lq2/2 J/d [q/2\, |ro| < [q2/2\) is a cyclic t-adic expansion, then 4 = xo - XiT + X2T - X3T = ro - T(xo - XiT + X2T2 - X3T3) is is a cyclic T-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) = T4 ± 9T3 + 38T2 ± 81T + 81, P(T) = T4 - 5T3 + 15T2 - 25T + 25 or P(T) = T6-7T5+21T4-49T3+147T2-343T+343 will lead to cyclic T-adic expansions. For q = g = 2, only the non-supersingular curves with P (T) = T4 ± 2T3 + 2T2 ± 4T + 4 lead to cyclic t-adic expansions. For q = 3 and g = 2, only the non-supersingular curves with P(T) = T4 ± 2T3 + 2T2 ± 6T + 9 or T4 ± T3 -2T2 ± 3T + 9 or T4 ± 3T3 + 5T2 ± 9T + 9 will lead to cyclic T-adic expansions. Based on Hasse-Weil Theorem, that is, (^/q - 1)2g < Pc (Fq) < (^q + 1)2g,if q is an integer such that (^q - 1)2g > qg/2, then, the corresponding hyperelliptic curves will not lead to cyclic expansion. For g = 2, 3 and 4, we have q > 37, 83 and 139, respectively. If the curve C with P(T) leads to cyclic expansion, then by Theorem 3, P(1) < [qg/2\ or P(-1) < [qg/2J, hence we can add ±(P(1) - qg) or ±(P(-1) - qg) to the coefficient set to make the expansion finite. For example, if the coefficient set is {0, ±1, • • • , ±39, ±40} |J{±51}, then for the hyperelliptic curves with P (T) = T4 ± 9T3 + 38T2 ± 81T + 81, all t-adic expansions are finite. 6 Optimizing the length of the t-expansion Let p = bo + biT +-----+ b2g-iT29-1 e Z[t], then since P(T) is irreducible, P(T) and B(T) = bo + biT +-----+ b2g-iT2g-i arecoprime. Hence, there exist polynomials U(T), V(T) e Z[T] such that U (T)B(T) + V (T)P (T) = 1. Replace T with t, we have p-i = U(t) e Z[t]. That is, we can use the extended Euclidean algorithm to compute the inverse of any element of Z[t]. For any divisor D e J(Fq"), we have 0n(D) = D. Furthermore, by Lemma 1, we have 2g 2g 2g n-i q" ) ^(1 - TP) ^(1 - Ti^ Tj ). i=i = i j=0 If for some D e J(Fq"), 0(D) = D, that is, (1 - t)D =< 1, 0 >, then n?£i(1 - Ti)D =< 1, 0 >, that is, J(Fq)D =< 1, 0 >. For practical cryptosystems, the divisor D should be chosen to be of large order. Hence, P(Fq)D =< 1, 0 > generally does not hold. Thus, for a large multiplier m, we can obtain the divisor multiplication mD by computing mD with m = m mod (tp - 1) or m mod (tt —ii). Similar to Theorem 3.1 in (8), we have the following Lemma 5. Lemma 5 For any positive integers n and m, there exists m e Z[t], such that 1. m = m mod (tp - 1), 2. N (m) . We can prove this lemma by letting s = m/(Tn - 1) = 2g-1 2g-1 E SiTi e Q[t], r = J2 [si+1/2\Ti and m = m-r(Tn-1). i=o i=o 2g-1 By letting a = m(T - 1)/(tp - 1) = J2 aT e Q[t], i=o 2g-1 Y = E [ai + 1/2\Ti e Z[t] and m = m - 7(tp - 1)/(t - 1), i=o we can prove the following Lemma 6. Lemma 6 For any positive integers n and m, there exists m e Z[t], such that 1. m = m mod ((tn - 1)/(t - 1)), 2. N (m) . 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 g over Fq, and let t be a root of C 's irreducible characteristic polynomial P(T). If C does not lead to cyclic t-adic expansions, then for a large positive integer m, m is congruent, modulo Tn - 1 or (t n — 1) / (t -1), to a t-adic expansion of length at most n+4g+5 or n + 4g + 4, respectively. If C leads to cyclic t-adic expansions, then this conclusion still holds if P(-1) - qg or P(1) - qg 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 ao = 1, P[¿] = aiqg-i and P[g + i] = ag-i for i = 1,...,g. Algorithm 1 Compute scalar multiplication by t-adic Expansion Input: a large positive integer multiplier m and a divisor D e J (Fq" ). Output: mD. I) f rFor>mp 234 Informatica 34 (2010) 227-236 L. You et al. and store it as Dr, 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 (t" — 1) : 1. Find integers s[i] such that 2g-1 s = ^^ s[i]Ti = Tn — 1 : ¿=0 1) Initialize s[i] := —P[i] for 0 < i < 2g — 1. 2) For k from 1 to n — 2g, do (a) A := s[2g — 1]. (b) For i from 1 to 2g — 1, set s[i] := s[i — 1] — P[i]A, and s[0] := —P[0]A. 3) Set s[0] := s[0] — 1. 2g-1 4) Set s := £ s[i]Ti. ¿=0 2. Applying Extended Euclidean Algorithm, there exist t, u e Z[t] with degTt < 2q — 1, such that t ■ s + u ■ P (t) = 1. 3. For t :=£2=-1 tiTi, set 2g-1 a : = Vm ■ ti + 1/2jTi. ¿=0 4. Set m : = m — sa mod P(t). III) Supposing m = E ¿=-1 m¿ti and converting m into a t-adic expansion: 1. j := 0; k := 0. 2. If m = 0, then do (a) Select rj e { — \qs/21 + 1,..., —1, 0,1,..., Vqg/2J} such that qg | (m0 — rj). (b) Set d := (mo — rj)/qg. 2g-2 (c) Set m := J2 (m¿+1 — P[i + 1]d)Ti — dT2g-1. ¿=0 (d) Set j := j + 1 and k := k + 1, and go back. IV) Computing mD : 1. Initialize B := Drk-1. 2. For i from k — 2 downto 0 do (a) Set B := 0(B). (b) Set B := B + Dr,. V) Output B as mD. Since the multiplier m can also be reduced by modulo (t" — 1)/(t — 1), Steps 1 in Step II) can be replaced by the following steps: Step II*) Computing m mod (t" — 1)/(t — 1): 1. Find integers s[i] such that 2g-1 s = E s[i]Ti = (t" — 1)/(t — 1): ¿=0 1) Initialize 0 < i < 2g — 1, set s[i] := 1 — P[i] and t[i] := —P[i]; 2) For k from 1 to n — 2g — 1 do (a) Set A := t[2g - 1] and t[0] := -P[0]A; (b) For i from 1 to 2g - 1, set t[i] := t[i - 1] - P[i]A and s[i] := s[i] + t[i]; 2g-1 3) Set s := £ s[i]Ti; i=0 Note that if P(1) < [qg/2J or P(-1) < [qg/2J, then add P(1) - qg or P(-1) - qg to the coefficient set. Take P(1) < qg/2 for example, we only make some minor modifications in Algorithm 1 as follows: First, add the computation of ±(qg -P (1))^ in the precompu-tation step; Second, change the step (a)-(b) in Step III) as follows: (a*) If \rho| < Lqg/2J or rh0 = P(1)-qg, then set rj := mo, otherwise, go to the next step: (b*) Select rj £ {P (1) - qg, -\qg/2 \ +1, •• • , -1, 0, 1, •• • , [qg/2J} such thatqg\(m0 - rj). 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 t-adic expansions of the multipliers approximate to the Jacobian group orders, and the average lengths (1)-(2) and densities (1)-(2) of the t-adic expansions of the multipliers after reduced by modulo (tn - 1)/(t - 1) or (tn - 1), respectively. The density means the ratio of the number of the non-zero coefficients to the length in a t-adic expansion. The corresponding characteristic polynomials of the five hy-perelliptic curves in Table 1 are T4 + 2T3 + 3T2 + 4T + 4, T4 - 2T3 + 2T2 - 6T + 9, T6 + 2T4 - 2T3 + 4T2 + 8, T4 - 4T3 + 11T2 - 20T + 25, and T6 + 2T5 + 4T4 + 14T3 + 20T2 + 50T + 125, respectively. Table 1 shows that, when the multipliers are reduced by modulo (tn - 1)/(t - 1) or tn - 1, the average lengths of the t-adic expansions are between n - 2 and n + g, or between n + 1 and n + g +1, respectively. It also shows that, if the multipliers are not reduced, then the average length of t-adic expansions is about qg 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 ~ qgn (near to the Jacobian order). Then, to compute mD, the binary method needs on average ng log2 q divisor additions and ng log2 q divisor doublings. While according to our experiments, Algorithm 1 needs on average n+1 divisor additions and g log2 q-1 divisor doublings, plus about n + | 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 tn - 1 or (tn - 1)/(t - 1), and show that the upper bound of the lengths of the reduced multipliers' t-adic expansions is n + 4g + 5. In addition, our experiment results show that the lengths of the multipliers' t-adic expansions FAST SCALAR MULTIPLICATIONS. Informatica 34 (2010) 227-236 235 bits reduced reduced reduced reduced Hyperelliptic curves q n of average average average average average average orders length density length(1) density(1) length(2) density(2) 61 122 242.125 0.749 62.000 0.761 62.833 0.756 67 134 264.250 0.738 64.667 0.732 68.000 0.733 v2 + (u2 + u + 1)v = u5 + u4 + u3 + u 2 73 146 291.000 0.758 70.500 0.756 73.000 0.752 89 178 355.000 0.736 87.833 0.784 87.500 0.760 113 226 451.000 0.741 110.667 0.768 112.333 0.712 61 194 244.000 0.832 61.833 0.865 62.000 0.869 67 213 267.500 0.828 67.667 0.872 68.167 0.905 v2 = u5 + u4 — u3 + u2 — u + 2 3 97 308 386.833 0.844 97.667 0.887 99.500 0.901 103 327 412.333 0.826 104.500 0.890 105.333 0.889 113 359 452.000 0.824 112.667 0.873 114.667 0.903 29 87 168.400 0.828 30.333 0.890 29.667 0.832 37 111 210.000 0.861 37.667 0.858 38.333 0.878 v2 + v = u7 + u6 + u5 2 43 129 254.000 0.867 42.833 0.883 45.500 0.865 59 177 352.000 0.845 60.500 0.859 59.833 0.847 67 201 398.000 0.865 67.167 0.868 70.000 0.877 61 284 246.000 0.906 62.167 0.949 64.000 0.958 67 312 270.000 0.916 68.667 0.973 70.500 0.962 v2 = u5 + u4 + 2u3 + u2 + u + 2 5 71 330 285.600 0.936 72.167 0.972 74.167 0.951 79 367 318.000 0.936 81.167 0.955 81.667 0.943 83 386 334.000 0.930 84.500 0.955 85.167 0.967 29 203 174.000 0.986 31.667 0.984 33.500 0.985 31 216 186.000 0.985 33.667 0.980 34.833 0.990 v2 = u7 + u5 + u3 + u — 1 5 37 258 222.000 0.998 40.833 0.988 40.333 0.979 43 300 258.000 0.979 44.167 0.985 47.333 0.986 53 370 318.000 0.991 55.167 0.988 57.667 0.991 Figure 1: Average Lengths and Densities of t-adic Expansions are actually between n — 2 and n + g +1. While Gunther et al(8) did experimentally show that the two hyperelliptic curves v2 + uv = u5 + au2 + 1 (a = 0,1) have some t-adic expansions of length about n + | (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 4'z(rjD) for 1 < i < n + 4g + 4 and — [qB/2J +1 < j < [qB/2J 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 Ec (Fq™) is isomorphic to the Jacobian group JC (Fq™) 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 Ec (Fq™). 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 Zhe-jiang 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. 918iC924. [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, IT-24(1), pp.106iC110. [5] A. Weil(1949). Number of solutions of equations in finite fields. Bull. AMS. 55, pp.497-508. [6] V. Müller(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. Günther, 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. 321337. 236 Informatica 34 (2010) 227-236 L. You et al. [11] A. Enge(2001). The Extended Euclidean Algorithm on Polynomials. and the Com-putational Efficiency of Hyper-elliptic 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.