Hyperelliptic Curves

Given an algebraic curve, we can form its Jacobian, namely the group of

divisors of degree 0 modulo principal divisors. As we saw in Corollary 11.4,

the Jacobian of an elliptic curve gives the same group as the elliptic curve.

However, for other curves, we get something new. In this chapter, we discuss

hyperelliptic curves, for which the theory can be carried out rather explicitly.

In [62], Koblitz suggested using hyperelliptic curves to build cryptosystems.

Of course, whenever we have a group, we can build cryptosystems whose

security depends on the di¬culty of solving the discrete logarithm problem

in the group. But computations in the group, for example adding elements,

need to be fast if the cryptosystem is to have practical value. In Section

13.3, we discuss Cantor™s algorithm, which allows us to compute in Jacobians

of hyperelliptic curves. In Section 13.4, we show how a form of the index

calculus can be used to attack the discrete logarithm for these Jacobians. It

turns out that this attack is e¬ective when the genus (an invariant attached

to the curve; see Theorem 11.15) is large. Therefore, it appears that the best

curves for cryptography have genus 2. For much more on hyperelliptic curves,

see [27], for example.

13.1 Basic De¬nitions

Let K be a ¬eld. Throughout Sections 13.1, 13.2, and 13.3, we assume that

K is algebraically closed, so that all points we consider have coordinates in K.

Let g ≥ 1 be an integer and let h(x) and f (x) be polynomials with coe¬cients

in K such that deg f = 2g + 1 and deg h ¤ g. Also, assume that f is monic

(that is, the coe¬cient of x2g+1 is 1). The curve C given by the equation

C : y 2 + h(x)y = f (x) (13.1)

is called a hyperelliptic curve of genus g if it is nonsingular for all x, y ∈

K. This means that no point (x, y) on the curve, with x, y ∈ K, satis¬es

2y + h(x) = 0 = f (x) ’ yh (x). When g = 1, we obtain an elliptic curve in

407

© 2008 by Taylor & Francis Group, LLC

408 CHAPTER 13 HYPERELLIPTIC CURVES

generalized Weierstrass form. It can be shown that the genus of C (in the

sense of Theorem 11.15) is g.

If the characteristic of K is not 2, we can complete the square on the left

side and put the curve into the form

C : y 2 = f (x), (13.2)

with f monic of degree 2g + 1. The nonsingularity condition states that no

point on the curve satis¬es 2y = 0 = f (x). Since y = 0 means that f (x) = 0,

this is equivalent to saying that no x satis¬es f (x) = 0 = f (x). In other

words, f (x) has no multiple roots, just as for the Weierstrass form of an

elliptic curve. For simplicity, we work with the form (13.2) throughout this

chapter.

There is one point at in¬nity, given by (0 : 1 : 0) and denoted ∞. If g ≥ 2,

this point is singular, but this has no e¬ect on what we do in this chapter.

Technical point: Various results that we need to apply to C require that

the curve be nonsingular. Therefore, it is necessary to remove the singularity

at in¬nity. This is done by taking what is called the normalization of C.

Fortunately, the resulting nonsingular curve agrees with C at the a¬ne (that

is, non-in¬nite) points and has a unique point at in¬nity (see, for example,

[106]), which we again denote ∞. In the following, we will be working with

functions and divisors. It will be easy to see what happens at the a¬ne points.

The behavior at ∞, which might seem harder to understand, is forced. For

example, the function x ’ a, where a is a constant, has two zeros, namely

(a, f (a)) and (a, ’ f (a)). Since the function has no other zeros or poles in

the a¬ne plane, and the degree of its divisor is 0, it must have a double pole at

∞. Similarly, any polynomial in x, y gives a function that has no poles in the

a¬ne plane, so the poles are at ∞. In fact, it can be shown that the rational

functions on C with no poles except possibly at ∞ are the polynomials in x, y.

In summary, in most situations we can work with ∞ without worry. However,

the point (more accurately, a neighborhood of the point) is more complicated

than it might appear.

REMARK 13.1 There are also hyperelliptic curves given by equations of

the forms (13.1) and (13.2) with deg f = 2g + 2. However, these will not be

used in this chapter. Therefore, throughout this chapter, hyperelliptic curve

will mean a curve with deg f = 2g + 1.

Let P = (x, y) be a point on C. De¬ne

w(P ) = (x, ’y),

which is also a point on C. The map w : P ’ w(P ) is called the hyperelliptic

involution. It satis¬es w(w(P )) = P for all points P on C. On elliptic curves,

w is multiplication by ’1.

© 2008 by Taylor & Francis Group, LLC

409

SECTION 13.2 DIVISORS

13.2 Divisors

We continue to assume that C is a hyperelliptic curve given by (13.2) over

an algebraically closed ¬eld K of characteristic not equal to 2.

In general, a line intersects C in 2g + 1 points. Therefore, when g ≥ 2, we

cannot use the method from elliptic curves to make the points on C into a

group, since the line through two points intersects the curve in 2g’1 additional

points, rather than in a unique third point. Instead, we form the group of

divisors of degree 0 modulo principal divisors (that is, modulo divisors of

functions on C).

In order to discuss divisors of functions, we need to make precise the order

of vanishing of a function at a point. Let P = (a, b) be a point on C and let t

be a function that has a simple zero at P . If H(x, y) is a function on C, write

H = tr G, where G(P ) = 0, ∞. Then H has a zero of order r at P (if r < 0,

then H has a pole of order |r|). If P = (a, b) with b = 0, it can be shown that

t = x ’ a has a simple zero at P . If b = 0, then x ’ a has a double zero, but

t = y works since the function y has a simple zero. The intuition is that the

line x ’ a = 0 intersects the curve C nontangentially at (a, b) except when

b = 0, where it is a vertical tangent to the curve. Since tangency corresponds

to higher order vanishing (as in Section 2.4), we need to use y instead, since

the horizontal line y = 0 intersects C at (a, 0) nontangentially.

The functions we will work with are polynomials in x and y. Since y 2 =

f (x), we can replace y 2 with f (x). By induction, any polynomial in x, y can

be reduced to a function of the form A(x) + B(x)y, where A(x) and B(x) are

polynomials in x.

We need to consider two special forms of functions.

PROPOSITION 13.2

(a) Let A(x) = j (x ’ aj )cj . Then

cj [Pj ] + [w(Pj )] ’ 2[∞] ,

div(A(x)) =

j

where Pj = aj , f (aj ) and w(Pj ) = aj , ’ f (aj ) .

(b) Let V (x) be a polynomial. Let

f (x) ’ V (x)2 =

dj

(x ’ aj ) .

j

Then the function y ’ V (x) has divisor

div y ’ V (x) = dj [(aj , bj )] ’ [∞] ,

j

© 2008 by Taylor & Francis Group, LLC

410 CHAPTER 13 HYPERELLIPTIC CURVES

where bj = V (aj ). If bj = 0, then dj = 1.

Let a ∈ K. Consider the function given by the polynomial

PROOF

H(x, y) = x ’ a. If f (a) = 0, this function has simple zeros at P = (a, f (a))

and at w(P ) = (a, ’ f (a)). The only possible pole of x ’ a is at ∞. Since

the number of zeros equals the number of poles (Proposition 11.1), there is a

double pole at ∞. Therefore,

div(x ’ a) = [P ] + [w(P )] ’ 2[∞].

If f (a) = 0, then

x’a

x ’ a = y2 .

f (x)

Since f (x) has no multiple roots, (x’a)/f (x) does not have a zero or a pole at

(a, 0). Therefore, x ’ a has a double zero at (a, 0). Note that w(a, 0) = (a, 0),

so we can also write div(x ’ a) in the form [P ] + [w(P )] ’ 2[∞] in this case.

If A(x) = j (x ’ aj )cj , then div(A(x)) = j cj ([Pj ] + [w(Pj )] ’ 2[∞]),

where Pj = aj , f (aj ) (for either choice of sign for the square root). We

will use this for polynomials A(x), but it also applies when cj < 0 is allowed,

hence when A(x) is a rational function.

Consider now a function of the form y ’ V (x), where V (x) is a polynomial.

Let P = (a, b) be a point on C with b = 0. Assume that y ’ V (x) has a zero

at P , so V (a) = b. Since b = 0, we have V (a) + b = 0, so the function y + V (x)

does not have a zero at P . Therefore, the order of vanishing of y ’ V (x) at P

is the same as the order of vanishing of

y + V (x) y ’ V (x) = y2 ’ V (x)2 = f (x) ’ V (x)2 .

We conclude that, when b = 0 and b = V (a), the coe¬cient of (a, b) in

div(y ’ V ) equals the multiplicity of x ’ a in the factorization of f ’ V 2 .

Now suppose (a, 0) is a point on C at which y ’ V (x) has a zero. This

means that f (a) = 0 and V (a) = 0. Since the function x ’ a has a double zero

at (a, 0), the function V (x) has at least a double zero at (a, 0). But y has a

simple zero at (a, 0), so the function y ’ V (x) has only a simple zero at (a, 0).

Suppose (x ’ a)2 is a factor of the polynomial f (x) ’ V (x)2 . Since (x ’ a)2 is

a factor of V (x)2 , it is also a factor of f (x), which is not possible since f (x)

has no multiple roots. Therefore, the polynomial f (x) ’ V (x)2 has x ’ a as

a simple factor. In other words, if V (a) = 0 and (a, 0) is on C, the divisor of

y ’ V (x) contains [(a, 0)] with coe¬cient 1, and the polynomial f (x) ’ V (x)2

has x ’ a as a simple factor.

So far, we have proved that every zero of y ’ V gives a root of f ’ V 2 . We

need to show that f ’ V 2 has no other roots. Write

div(y ’ V ) = dj ([(aj , bj )] ’ [∞]) .

j

© 2008 by Taylor & Francis Group, LLC

411

SECTION 13.2 DIVISORS

Then

dj ([(aj , ’bj )] ’ [∞]) = dj ([w(aj , bj )] ’ [∞]) .

div(y + V ) =

j j

Since

div(f ’V 2 ) = div(y +V )+div(y ’V ) = dj ([(aj , bj )] + [(aj , ’bj )] ’ 2[∞]) ,

j

we must have f ’ V 2 = ’ aj )dj , by part (a). Therefore, every root of

j (x

f ’ V 2 yields a term in div(y ’ V ). This completes the proof.

Part (a) of the proposition has a converse. If D = cj [Pj ] is a divisor, let

w(D) = cj [w(Pj )].

PROPOSITION 13.3

Let D be a divisor of degree 0. Then D + w(D) is a principal divisor; in fact,

it is the divisor of a rational function in x.

PROOF Write D = j cj [Pj ], where possibly some Pj is ∞. Since deg D =

j cj ([Pj ] ’ [∞]). If some Pj = ∞, that

0, we have j cj = 0, so D =

term can now be omitted, so we may assume Pj = ∞ for all j. Therefore,

D+w(D) = j cj ([Pj ] + [w(Pj )] ’ 2[∞]), which is the divisor of a polynomial

in x, by Proposition 13.2.

A divisor of the form D = j cj ([Pj ] ’ [∞]), with Pj = (aj , bj ), is called

semi-reduced if the following hold:

1. cj ≥ 0 for all j

2. if bj = 0, then cj = 0 or 1

3. if [Pj ] with bj = 0 occurs in the sum (that is, cj > 0), then [w(Pj )] does

not occur.

If, in addition, j cj ¤ g, then D is called reduced.

Proposition 13.2 implies that div (y ’ V (x)) is semi-reduced for every poly-

nomial V (x).

Let D1 = j cj ([Pj ] ’ [∞]) and D2 = j dj ([Pj ] ’ [∞]) be two divisors

with cj ≥ 0 and dj ≥ 0. De¬ne

min{cj , dj } ([Pj ] ’ [∞]) .

gcd(D1 , D2 ) =

j

© 2008 by Taylor & Francis Group, LLC

412 CHAPTER 13 HYPERELLIPTIC CURVES

PROPOSITION 13.4

Let D = j cj ([Pj ] ’ [∞]) be a semi-reduced divisor. Let Pj = (aj , bj ) and

U (x) = j (x ’ aj )cj . Let V (x) be a polynomial such that bj = V (aj ) for all

j. Then

D = gcd div(U (x)), div(y ’ V (x) ⇐’ f (x) ’ V (x)2 is a multiple of U (x)

(that is f (x) ’ V (x)2 is a polynomial multiple of U (x)).

PROOF In the notation of Proposition 13.2(b), dj ≥ cj for all j if and

only if f (x) ’ V (x)2 is a multiple of U (x). The gcd is D if and only if dj ≥ cj

for all j, which yields the result. It is worth mentioning what happens at the

points (aj , bj ) in D where bj = 0. Since D is semi-reduced, cj = 1 for these

points. Although div(x’aj ) contains 2[Pj ]’2[∞], the gcd contains [Pj ]’[∞]

only once since div(y ’ V (x)) contains [Pj ] ’ [∞] only once.

The following result is central to our treatment of divisors for hyperelliptic

curves, since it allows us to represent divisors concretely as pairs of polyno-

mials.

THEOREM 13.5

There is a one-to-one correspondence between semi-reduced divisors D =

j cj ([Pj ] ’ [∞]) and pairs of polynomials (U (x), V (x)) satisfying

1. U (x) is monic,

2. deg U (x) = j cj and deg V (x) < deg U (x),

3. V (x)2 ’ f (x) is a multiple of U (x).

Under this correspondence, D = gcd div(U (x)), div(y ’ V (x) .

PROOF Given a pair (U, V ), we obtain a divisor D as the gcd, as in the

statement of the theorem. Since div(y ’ V (x)) is semi-reduced, the gcd is

semi-reduced. Proposition 13.4 tells us that deg U (x) = j cj , as desired.

Conversely, suppose we have a semi-reduced divisor D. Let Pj = (aj , bj ) be

a point occurring in D. We can construct U (x) as in Proposition 13.4, but

we need to ¬nd V (x) such that V (aj ) = bj for all j and such that V 2 ’ f is

a multiple of U . For this, we use a square root algorithm.

Write U (x) = j (x ’ aj )cj . Suppose that, for each j, we have Vj (x) such

that Vj (aj ) = bj and Vj (x)2 ≡ f (x) (mod (x ’ aj )cj ). The Chinese remainder

theorem for polynomials (Exercise 13.10) tells us that there is a polynomial

V (x) such that V (x) ≡ Vj (x) (mod (x’aj )cj ) for all j. Then V (x)2 ’f (x) ≡ 0

(mod (x’aj )cj ) for all j. This implies that V (x)2 ’f (x) is a multiple of U (x).

Also, V (x) ≡ Vj (x) (mod x ’ aj ) implies that V (aj ) = Vj (aj ) = bj .

© 2008 by Taylor & Francis Group, LLC

413

SECTION 13.2 DIVISORS

The problem is now reduced to solving congruences of the form W (x)2 ≡

f (x) (mod (x’a)c ) with W (a) = b, where b2 = f (a). The solutions W will be

the desired polynomials Vj . If b = 0, then f (a) = 0 and, by Proposition 13.2,

we know that c = 1, so we can take W (x) = 0. This yields

W (x)2 = 02 = f (a) ≡ f (x) (mod (x ’ a))

since f (x) ≡ f (a) (mod (x ’ a)) for any polynomial f (x). Suppose now that

b = 0. Let W1 (x) = b. Then W1 (x)2 = b2 = f (a), so W1 (x)2 ’ f (x) is 0 at

x = a, hence is 0 mod x ’ a. Now suppose that 1 ¤ n < c and that we have

found Wn (x) such that Wn (x)2 ≡ f (x) (mod (x ’ a)n ) and Wn (a) = b. Write

Wn+1 (x) = Wn (x) + k(x ’ a)n

for some constant k to be determined. Then

Wn+1 (x)2 ’ f (x) ≡ Wn (x)2 ’ f (x) + 2k(x ’ a)n Wn (x) (mod (x ’ a)n+1 ).

Since Wn (x)2 ’ f (x) is a multiple of (x ’ a)n , we can form the polynomial

P (x) = Wn (x)2 ’ f (x) /(x ’ a)n . Let k = ’P (a)/2. Then Wn+1 (x)2 ’ f (x)

is a multiple of (x ’ a)n+1 . Continuing in this way, we obtain a function

W (x) = Wc (x) that has the desired properties. (Remark: This method is

actually the same as Newton™s method for ¬nding numerical approximations

to solutions of equations.)

As mentioned previously, we combine the functions Vj (x) via the Chinese

remainder theorem to obtain V (x). Now that we have a function V (x) with

V (x)2 ’ f (x) divisible by U (x), we can reduce V mod U to get a new function

V with deg V (x) < deg U (x). We have therefore found the desired pair (U, V ).

Finally, we need to show that V (x) is uniquely determined by D. Suppose

V1 (x) and V2 (x) are two such polynomials. The functions y ’ Vi (x) vanish

to order at least cj at Pj , and therefore their di¬erence V2 (x) ’ V1 (x) must

also vanish to this order. Therefore, V2 (x) ’ V1 (x) has at least j cj =

deg U (x) zeros, counting multiplicity. But deg(V2 (x) ’ V1 (x)) < deg U (x), so

V1 (x) ’ V2 (x) must be identically 0. This completes the proof.

The next result shows that the reduced divisors represent all divisor classes

of degree 0.

PROPOSITION 13.6

Let D be a divisor of degree 0 on C. There exists a unique reduced divisor

D1 such that D ’ D1 is a principal divisor.

PROOF Recall the Riemann-Roch theorem (Theorem 11.15): For any

divisor D,

(D) ’ (K ’ D) = deg(D) ’ g + 1.

© 2008 by Taylor & Francis Group, LLC

414 CHAPTER 13 HYPERELLIPTIC CURVES

Replace D with D + g[∞]. Then

(D + g[∞]) = (K ’ D ’ g[∞]) + 1 ≥ 1,

since (K ’ D ’ g[∞]) ≥ 0. This means that there is a function F = 0 such

that

div(F ) + D + g[∞] ≥ 0.

Let D1 = div(F ) + D, which is in the same divisor class as D. Then D1 +

g[∞] ≥ 0 and deg(D1 ) = 0. Since adding a multiple of [∞] to D1 makes

all coe¬cients nonnegative, and since deg(D1 ) = 0, it follows easily that the

only point in D1 with negative coe¬cients is [∞] and that there are at most g

other points in the sum. If D1 contains both [P ] and [w(P )] for some P , then

subtracting an appropriate multiple of the principal divisor [P ]+[w(P )]’2[∞]

removes either [P ] or [w(P )] from D1 and leaves the other with a nonnegative

coe¬cient. Therefore, we may assume that D1 is reduced, and hence D1 is

the required divisor.

We now show that D1 is unique. Suppose D ’ D1 = div(F ) and D ’ D2 =

div(G) with both D1 and D2 reduced. Then

D1 + w(D2 ) = D + w(D) ’ div(F ) ’ w(div(G)),

which is principal, since D + w(D) is principal (Proposition 13.3) and w

applied to a principal divisor yields a principal divisor (Exercise 13.4). Write

D1 + w(D2 ) = div(H). Then

div(H) + 2g[∞] = D1 + g[∞] + w D2 + g[∞] ≥ 0,

so H ∈ L(2g[∞]) (see Section 11.5).

The Riemann-Roch theorem says that

(2g[∞]) ’ (K ’ 2g[∞]) = 2g ’ g + 1 = g + 1.

Since deg(K ’ 2g[∞]) = ’2 < 0 by Corollary 11.16, we have (K ’ 2g[∞]) = 0

by Proposition 11.14. Therefore, (2g[∞]) = g + 1. Since xj ∈ L(2j[∞]), the

set

{1, x, x2 , . . . , xg }

gives g + 1 functions in L(2g[∞]). They are linearly independent since they

have poles of distinct orders. Therefore, they form a basis of L(2g[∞]). This

means that every element can be written as a polynomial in x of degree at

most g.

We conclude that D1 + w(D2 ) = div(H), where H is a polynomial in x. As

we showed earlier, this means that

cj ([Pj ] + [w(Pj )] ’ 2[∞])

D1 + w(D2 ) =

j

© 2008 by Taylor & Francis Group, LLC

415

SECTION 13.2 DIVISORS

for some points Pj and some integers cj . Since D1 and w(D2 ) are reduced,

[Pj ] occurs in one of D1 and w(D2 ), and [w(Pj )] occurs in the other. By

switching the names of Pj and w(Pj ), if necessary, we may assume that

([Pj ] ’ [∞]) ([w(Pj )] ’ [∞]).

D1 = and w(D2 ) =

j j

This implies that D1 = D2 , as desired.

We refer to elements of the group of divisors of degree 0 modulo principal

divisors as divisor classes of degree 0. The set of divisor classes of degree

0 can be given the structure of an algebraic variety, called the Jacobian

variety J of C. Over the complex numbers, the Jacobian has the structure

of a g-dimensional complex torus Cg /L, where L is a lattice in g-dimensional

complex space (the case g = 1 is the case of elliptic curves treated in Chapter

9). The addition of divisor classes corresponds to addition of points in Cg /L.

Let P1 , P2 be points on C. Since [P1 ] ’ [∞] and [P2 ] ’ [∞] are reduced, the

uniqueness part of Proposition 13.6 implies that these two divisors are not

equivalent modulo principal divisors. Therefore, the map

C ’’ J

P ’’ [P ] ’ [∞]

gives an injective mapping of C into its Jacobian. In the case of elliptic curves,

this is an isomorphism (Corollary 11.4).

THEOREM 13.7

There is a one-to-one correspondence between divisor classes of degree 0 on

C and pairs (U (x), V (x)) of polynomials satisfying

1. U is monic.

2. deg V < deg U ¤ g.

3. V 2 ’ f (x) is a multiple of U .

PROOF By Proposition 13.6, every divisor class of degree 0 is represented

by a unique reduced divisor. By Theorem 13.5, these divisors are in one-to-

one correspondence with the pairs (U, V ) as in the statement of the present

theorem.

REMARK 13.8 The pair (U, V ) is called the Mumford representation

of the corresponding divisor class. In many situations, it is easier to work with

the Mumford representations than directly with the divisor classes. In the next

© 2008 by Taylor & Francis Group, LLC

416 CHAPTER 13 HYPERELLIPTIC CURVES

section, we describe an algorithm that produces the Mumford representation

for the sum of two divisor classes of degree 0.

If we start with a divisor of degree 0 where [∞] is the only point with

a negative coe¬cient, then it is easy to ¬nd a semi-reduced divisor in the

same divisor class; namely, we remove divisors of suitable polynomials in

x. However, the proof of Proposition 13.6 does not immediately give an

algorithm for changing the semi-reduced divisor to the reduced divisor in the

same divisor class. Nevertheless, if we work with the pair (U, V ) associated to

the semi-reduced divisor, there is a straightforward procedure that produces

the pair corresponding to the reduced divisor.

THEOREM 13.9 (Reduction Procedure)

Let (U, V ) be a pair representing a semi-reduced divisor D of degree 0. Do

the following:

1. Let U = (f ’ V 2 )/U .

˜

˜ ˜ ˜ ˜

2. Let V ≡ ’V (mod U ) with deg(V ) < deg U .

˜ ˜

3. Let U = U and V = V .

4. Multiply U by a constant to make U monic.

5. If deg(U ) > g, go back to step 1. Otherwise, continue.

6. Output (U, V ).

The reduction procedure terminates, and the output is the pair representing

the reduced divisor in the divisor class of D.

PROOF The divisor of U (x) is D + w(D). The divisor of y ’ V (x) is

D + E, where E has the form j ej ([Qj ] ’ [∞]) for some points Qj and some

coe¬cients ej ≥ 0. The divisor of y + V (x) is w(D + E). Since

U U = f ’ V 2 = (y + V )(y ’ V ),

˜

we have

˜ ˜

D + w(D) + div(U ) = div(U ) + div(U ) = D + E + w(D + E).

Therefore,

˜

div(U ) = E + w(E). (13.3)

Since div(y + V ) = w(D) + w(E),

˜

gcd div(U ), div(y + V ) = w(E) (13.4)

© 2008 by Taylor & Francis Group, LLC

417

SECTION 13.3 CANTOR™S ALGORITHM

(as remarked earlier, a divisor of the form div(y + V ) is semi-reduced, so it

cannot contain contributions from both E and w(E)). But

˜

D ’ div(y ’ V ) = ’E = w(E) ’ div(U ),

˜˜

so w(E) is in the same divisor class as D. We claim that (U , V ) represents

˜ ej , the number of summands

w(E). By (13.3), the degree of U equals

˜ 2 ≡ (’V )2 ≡ f (mod U ), Theorem 13.5 implies that (U , V )

˜ ˜˜

in E. Since V

represents a divisor. By (13.4), it represents w(E).

Finally, suppose deg(U ) ≥ g + 1. Then deg(f ) < 2 deg(U ) and deg(V 2 ) <

2 deg(U ), so deg(U )+deg(U ) = deg(f ’V 2 ) < 2 deg(U ). Therefore, deg(U ) <

˜ ˜

deg(U ). This means that the degree decreases at every iteration of steps (1)

through (4) until we obtain a polynomial of degree at most g. At this point,

the corresponding divisor is reduced and we are done.

13.3 Cantor™s Algorithm

Although very useful from a theoretical point of view, the description of

the points of the Jacobian J in terms of divisor classes of degree 0 is not very

useful from a computational point of view. On the other hand, the Mumford

representation gives a very concrete representation of points of J. In this

section, we present an algorithm due to David Cantor [22] for adding divisor

classes that are given by their Mumford representations. The algorithm has

its origins in Gauss™s theory of composition of quadratic forms.

THEOREM 13.10 (Cantor™s algorithm)

Let D1 and D2 be divisors of degree 0, whose classes correspond to pairs

(U1 , V1 ) and (U2 , V2 ), as in Theorem 13.7.

1. Let d = gcd(U1 , U2 , V1 + V2 ). Find polynomials h1 , h2 , h3 such that

d = U1 h1 + U2 h2 + (V1 + V2 )h3 .

2. Let V0 = (U1 V2 h1 + U2 V1 h2 + (V1 V2 + f )h3 ) /d.

3. Let U = U1 U2 /d2 and V ≡ V0 (mod U ) with deg V < deg U .

4. Let U = (f ’ V 2 )/U and V ≡ ’V (mod U ), with deg(V ) < deg U .

˜ ˜ ˜ ˜ ˜

˜ ˜

5. Let U = U and V = V .

6. Multiply U by a constant to make U monic.

7. If deg(U ) > g, go back to step 4. Otherwise, continue.

© 2008 by Taylor & Francis Group, LLC

418 CHAPTER 13 HYPERELLIPTIC CURVES

8. Output (U, V ).

The pair (U, V ) is the Mumford representation of the divisor class of D1 + D2 .

PROOF By modifying D1 and D2 by principal divisors, we may assume

that Di = gcd(div(Ui ), div(y ’Vi )), for i = 1, 2. The algorithm consists of two

parts. The ¬rst part, which is steps (1), (2), and (3), constructs a pair (U, V ).

It essentially corresponds to D1 +D2 , but terms of the form [P ]+[w(P )]’2[∞]

need to be removed. This is the role of the polynomial d(x). The second part,

steps (4) through (7), lowers the degree of U (x) so that deg U (x) ¤ g.

First, we need to check that V0 in step (2) is a polynomial. Since U1 , U2

are multiples of d, it remains to show that V1 V2 + f is a multiple of d. But

V1 V2 + f = V1 (V1 + V2 ) + f ’ V12 ≡ 0 (mod d),

since V1 + V2 is a multiple of d and since f ’ V12 is a multiple of U1 , hence a

multiple of d. Therefore, V0 is a polynomial.

We now show that gcd (U (x), y ’ V0 (x)) equals the semi-reduction of D1 +

D2 , namely, D1 + D2 with any terms of the form [P ] + [w(P )] ’ 2[∞] removed.

To do so, we need to explain the de¬nition of V0 (x). Consider a point P =

(a, b) and let the coe¬cient of [P ] ’ [∞] in Di be ri ≥ 0. The functions Ui

and y ’ Vi vanish to order at least ri at P . Therefore, the products

(y ’ V1 )U2 , (y ’ V2 )U1 , (y ’ V1 )(y ’ V2 ) = f + V1 V2 ’ (V1 + V2 )y

U1 U2 ,

vanish to order at least r1 + r2 at P . The coe¬cients of y in the last three

functions are U2 , U1 , ’(V1 + V2 ), and the polynomial d is the gcd of these.

The linear combination for d in step (1) implies that

(y ’ V2 )U1 h1 + (y ’ V1 )U2 h2 + ((V1 + V2 )y ’ f ’ V1 V2 ) h3

= dy ’ dV0 .

Therefore, (y ’ V0 )d vanishes to order at least r1 + r2 at P .

We now need to consider in detail what happens at each point P = (a, b).

It is convenient to work with both P and w(P ) = (a, ’b) at the same time.

For simplicity, let (U, y ’ V ) denote the divisor gcd(div(U ), div(y ’ V )).

Write

(U1 , y ’ V1 ) = D1 = r1 ([P ] ’ [∞]) + s1 ([w(P )] ’ [∞]) + · · ·

(U2 , y ’ V2 ) = D2 = r2 ([P ] ’ [∞]) + s2 ([w(P )] ’ [∞]) + · · · .

Since D1 and D2 are semi-reduced, either r1 = 0 or s1 = 0, and either r2 = 0

or s2 = 0.

We need to show that the coe¬cients of [P ] ’ [∞] and of [w(P )] ’ [∞] in

the semi-reduction of D1 + D2 match those in (U, y ’ V0 ), where U is the

polynomial obtained in step (3). There are several cases to consider.

© 2008 by Taylor & Francis Group, LLC

419

SECTION 13.3 CANTOR™S ALGORITHM

If r1 = s1 = r2 = s2 = 0, then U (P ) = 0. Therefore, P and w(P ) do not

occur in (U, y ’ V0 ) and they do not occur in D1 + D2 .

If some ri or si is positive, we can rename the points and divisors so that

r1 > 0, and r1 = Max(r1 , s1 , r2 , s2 ). Then s1 = 0. Henceforth, we assume

this is the case.

If r2 = s2 = 0, then d(P ) = 0. The order of U at P is the order of U1 at P ,

which is r1 . Since (y’V0 )d has order at least r1 at P , so does y’V0 . Therefore,

(U, y ’ V0 ) contains r1 ([P ] ’ [∞]). Since (U, y ’ V0 ) is semi-reduced, it does

not contain [w(P )] ’ [∞] (except when P = w(P )). Therefore, D1 + D2 and

(U, y ’ V0 ) agree at the terms involving [P ] ’ [∞] and [wP ] ’ [∞].

If r2 > 0 and b = 0, then U1 and U2 have simple zeros as polynomials (and

double zeros as functions on C) at a by Proposition 13.2. Also, V1 + V2 has

a zero at a, so the gcd d has a simple zero at a. Therefore, U = U1 U2 /d2 has

no zero at a, so the divisor corresponding to (U, V ) does not contain P . Since

U1 (a) = U2 (a) = 0, the divisors D1 and D2 both contain P = (a, 0) = w(P ).

By Proposition 13.2, they each contain [P ]’[∞] with coe¬cient 1. Therefore,

D1 + D2 contains 2 ([P ] ’ [∞]), which is principal and can be removed. The

resulting divisor does not contain P . Therefore, (U, y ’ V0 ) and the semi-

reduction of D1 + D2 agree at terms containing P .

From now on, assume that b = 0. If r2 > 0, then s2 = 0. Since V1 (a) =

V2 (a) = b = 0, we have V1 + V2 = 0 at P . Therefore, d(P ) = 0. Therefore, the

order of U at P is r1 + r2 . As pointed out previously, the order of (y ’ V0 )d at

P is at least r1 + r2 , so the order of y ’ V0 at P is at least r1 + r2 . Therefore,

(U, y ’ V0 ) contains (r1 + r2 ) ([P ] ’ [∞]), which matches D1 + D2 . Since

(U, y ’ V0 ) is semi-reduced, it has no terms with w(P ). Neither does D1 + D2 .

Finally, suppose s2 > 0. Then r2 = 0. Then y ’ V1 has order at least r1

at P and y ’ V2 has order at least s2 at w(P ). Therefore, V2 (a) = ’b, so

y ’ V2 takes the value 2b = 0 at P . Since (y + V2 )(y ’ V2 ) = f ’ V22 is a

multiple of U2 , which has order s2 at P , the order of y + V2 at P is at least

s2 . Therefore, the order at P of V1 + V2 = (V1 ’ y) + (y + V2 ) is at least

min(r1 , s2 ) = s2 , by the choice of r1 . It follows that d, which is the gcd of U1 ,

U2 , and V1 + V2 , has order exactly s2 at P , since this minimum is attained

for U2 . The order of U at P is therefore r1 + s2 ’ 2s2 = r1 ’ s2 . We know

that (y ’ V0 )d has order at least r1 at P . Similarly, it has order at least s2

at w(P ). Therefore, y ’ V0 has order at least r1 ’ s2 at P . If r1 ’ s2 > 0,

then (U, y ’ V0 ) contains (r1 ’ s2 ) ([P ] ’ [∞]). Since it is semi-reduced, it

does not contain [w(P )] ’ [∞]. If r1 ’ s2 = 0, then U (P ) = 0, so (U, y ’ V0 )

contains neither P nor w(P ). Therefore, (U, y ’ V0 ) agrees at P and w(P )

with D1 +D2 ’s2 ([P ] + [w(P )] ’ 2[∞]), hence agrees with the semi-reduction

of D1 + D2 .

We have therefore proved that (U, y ’V0 ) and the semi-reduction of D1 +D2

agree at all terms, so they are equal. Since (U, y ’ V ) = gcd(U, y ’ V0 ), this

completes the proof that the divisor represented by (U, V ) is in the divisor

class of D1 + D2 .

Note that we have proved that y ’ V0 vanishes at least to the order of

© 2008 by Taylor & Francis Group, LLC

420 CHAPTER 13 HYPERELLIPTIC CURVES

vanishing of U at each point (a, V0 (a)). By Proposition 13.4, f ’ V02 is a

multiple of U . Since V ≡ V0 (mod U ), f ’ V 2 is also a multiple of U , as

required.

Steps (4) through (7) are the reduction algorithm. Theorem 13.9 says that

this process yields the desired reduced divisor.

Example 13.1

Consider the curve C : y 2 = x5 ’ 1 over F3 . Let™s compute

x2 ’ x + 1, ’x + 1 + (x ’ 1, 0) .

We have U1 = x2 ’ x + 1, U2 = x ’ 1, V1 + V2 = ’x + 1. The gcd of these is

1, and

(x2 ’ x + 1) · 1 + (x ’ 1) · (’x) + (’x + 1) · 0 = 1,

so we may take h1 = 1, h2 = ’x, h3 = 0. We obtain

U = (x2 ’ x + 1)(x ’ 1) = x3 + x2 ’ x ’ 1,

V ≡ 0 + (x ’ 1)(’x + 1)(’x) + 0 = x3 + x2 + x ≡ ’x + 1 (mod U ).

The reduction procedure yields

(x5 ’ 1) ’ (’x + 1)2

= x2 ’ x ’ 1

˜

U=

U

˜

and V = x ’ 1. Therefore,

x2 ’ x + 1, ’x + 1 + (x ’ 1, 0) = x2 ’ x ’ 1, x ’ 1 .

13.4 The Discrete Logarithm Problem

Up to now, we have been working over an algebraically closed ¬eld. But now

we consider a curve and divisors de¬ned over a ¬nite ¬eld Fq . We continue

to assume that q is not a power of 2, so we can use (13.2) instead of (13.1).

We take f (x) in (13.2) to be a polynomial with coe¬cients in Fq and with

no multiple roots in Fq . Let φ be the q-th power Frobenius map. A divisor

D is said to be de¬ned over Fq if φ(D) = D (where φ([P ]) is de¬ned to be

[φ(P )] and φ([∞]) = [∞]). This means that φ can permute the summands of

D as long as it leaves the overall sum unchanged. A divisor class is said to

be de¬ned over Fq if φ(D) ’ D is a principal divisor for some (equivalently,

© 2008 by Taylor & Francis Group, LLC

421

SECTION 13.4 THE DISCRETE LOGARITHM PROBLEM

all) divisors D in the divisor class. These correspond to the points on the

Jacobian variety that are de¬ned over Fq . We denote this set by J(Fq ).

Suppose D is a divisor of degree 0 such that φ(D) is in the same divisor class

as D. The divisor class of D contains a unique reduced divisor R, and the

divisor class of φ(D) contains φ(R) (proof: D ’R = div(F ), so φ(D)’φ(R) =

div(φ(F ))), and φ(R) is also reduced. The uniqueness implies that R = φ(R).

Therefore, the divisor class contains a divisor ¬xed by φ. The reduced divisor

R corresponds to a unique pair (U, V ) of polynomials. The divisor φ(R)

corresponds to the pair (U φ , V φ ), where U φ denotes the polynomial obtained

by applying φ to the coe¬cients of U . Since φ(R) = R, we have U φ = U

and V φ = V , because the pair corresponding to a divisor is unique. It follows

that a divisor class that is mapped to itself by φ corresponds to a unique

pair (U, V ) of polynomials, with U, V ∈ Fq [x] (= the set of polynomials with

coe¬cients in Fq ). Conversely, if U, V ∈ Fq [x], then gcd (div(U ), div(y ’ V ))

is ¬xed by φ, hence yields a divisor class ¬xed by φ. We have proved the

following.

PROPOSITION 13.11

There is a one-to-one correspondence between J(Fq ) and pairs (U, V ) of poly-

nomials with coe¬cients in Fq satisfying

1. U is monic.

2. deg V < deg U ¤ g.

3. V 2 ’ f (x) is a multiple of U .

Since there are only ¬nitely many polynomials U ∈ Fq [x] of degree at most

g, there are only ¬nitely many divisor classes of degree 0 that are de¬ned over

Fq . In other words, J(Fq ) is ¬nite. It is easy to see that it is closed under

addition, so it forms a group. Alternatively, Cantor™s algorithm clearly takes

pairs of polynomials de¬ned over Fq to pairs de¬ned over Fq . In fact, we

could ignore the geometry completely and consider a group whose elements

are suitable pairs of polynomials and whose law of composition is given by

Cantor™s algorithm. This de¬nes a group (although the associativity might

be di¬cult to prove without the geometric interpretation).

Example 13.2

Let™s consider the case where deg U = 1. Then U = x ’ a for some a, and

V = b for some b ∈ Fq . Also, f (x) ≡ f (a) (mod x ’ a), so b2 = V 2 ≡ f (a),

hence b2 = f (a). This means that (a, b) is a point on the curve. The divisor

class for (U, V ) is de¬ned over Fq if and only if the polynomials x ’ a and

b have coe¬cients in Fq , which happens if and only if the point (a, b) has

coordinates in Fq .

© 2008 by Taylor & Francis Group, LLC

422 CHAPTER 13 HYPERELLIPTIC CURVES

Example 13.3

Let D = gcd(div(U ), div(y ’ V )), which corresponds to (U, V ), and suppose

that deg U = 2 where U is an irreducible polynomial in Fq [x]. We can factor

U as (x ’ a1 )(x ’ a2 ) over Fq2 . Then

D = [(a1 , V (a1 ))] + [a2 , V (a2 ))] ’ 2[∞].

Since a1 , a2 ∈ Fq , the points (ai , V (ai )) are not de¬ned over Fq . However, φ

interchanges [(a1 , V (a1 ))] and [(a2 , V (a2 ))], hence φ(D) = D.

Example 13.4

Let™s consider the curve C : y 2 = x5 ’ 1 over F3 . The points in C(F3 ) are

{∞, (1, 0), (’1, 1), (’1, ’1)}.

√

Denote the elements of F9 as a + bi with a, b ∈ {’1, 0, 1} and i = ’1. The

elements of C(F9 ) are

∞, (1, 0), (’1, 1), (’1, ’1), (0, i), (0, ’i),

(’1 + i, 1 + i), (’1 + i, ’1 ’ i), (’1 ’ i, 1 ’ i), (’1 ’ i, ’1 + i).

The pairs of polynomials (U, V ) corresponding to reduced divisors are

D ≡ (x2 ’ 1, x ’ 1), 2D ≡ (x2 ’ x + 1, x ’ 1), 3D ≡ (x2 ’ x ’ 1, x ’ 1),

4D ≡ (x + 1, ’1), 5D ≡ (x ’ 1, 0), 6D ≡ (x + 1, 1),

7D ≡ (x2 ’ x ’ 1, ’x + 1), 8D ≡ (x2 ’ x + 1, ’x + 1),

9D ≡ (x2 ’ 1, ’x + 1), 10D ≡ (1, 0)

(where “≡” denotes congruence modulo principal divisors). These can be

found by exhaustively listing all polynomials U of degree at most 2 with coef-

¬cients in F3 , and ¬nding solutions to V 2 ≡ x5 ’ 1 (mod U ) when they exist.

The pair (x + 1, 1) corresponds to the divisor gcd (div(x + 1), div(y ’ 1)) =

[(’1, 1)] ’ [∞]. The pair (x2 ’ x ’ 1, x ’ 1) corresponds to the divisor

[(’1 + i, 1 + i)] + [(’1 ’ i, 1 ’ i)] ’ 2[∞]. This can be seen as follows. The

roots of x2 ’ x ’ 1 are x = ’1 + i and x = ’1 ’ i. The polynomial V = x ’ 1

tells us that the y-coordinates satisfy y = x ’ 1, which yields y = 1 + i and

y = 1 ’ i. The points (’1 + i, 1 + i) and (’1 ’ i, 1 ’ i) are not de¬ned

over F3 individually. However, they are interchanged by the Frobenius map,

which maps i ’ i3 = ’i, so the divisor is left unchanged by Frobenius and

is therefore de¬ned over F3 . Similarly, the pair (x2 + 2x + 2, 2x + 1) corre-

sponds to the divisor [(’1 + i, ’1 ’ i)] + [(’1 ’ i, ’1 + i)] ’ 2[∞]. The divisor

[(0, i)] + [(0, ’i)] ’ 2[∞] is also de¬ned over F3 . What does it correspond to?

Observe that it is not reduced since w(0, i) = (0, ’i). Therefore, it must be

reduced ¬rst. Since it is of the form [P ] + [w(P )] ’ 2[∞], it is principal, so

© 2008 by Taylor & Francis Group, LLC

423

SECTION 13.4 THE DISCRETE LOGARITHM PROBLEM

it reduces to the trivial divisor, corresponding to the pair (1, 0). In fact, it is

the divisor of the function x on C.

Koblitz [62] proposed the discrete logarithm problem in groups of the form

J(Fq ) as the basis for cryptosystems such as those in Chapter 6. The ¬rst

question is how large is J(Fq )? It was proved by Weil, as a generalization of

Hasse™s Theorem, that

√ √

2g 2g

( q ’ 1) ¤ #J(Fq ) ¤ ( q + 1) .

Therefore, the “square root” attacks such as Baby Step, Giant Step and the

ρ and » methods from Chapter 5 work in time around q g/2 , which is approx-

imately the square root of the order of the group. However, for Jacobians of

hyperelliptic curves, there is an index calculus that is faster than the square

root algorithms when g ≥ 3. (On the other hand, for g = 2, it is possible

that the corresponding cryptosystems are more secure than those for elliptic

curves.) We now describe the method.

Recall that in the index calculus over the integers mod p, we needed the

notions of B-smoothness and of factorization into small primes. The following

result lets us de¬ne a similar notion for divisors.

PROPOSITION 13.12

Let (U, V ) be a pair of polynomials in Fq [x] representing a semi-reduced divi-

sor. Factor U (x) = i Ui (x) into polynomials in Fq [x]. Let Vi ≡ V (mod Ui )

with deg Vi < deg Ui . Then (Ui , Vi ) represents a semi-reduced divisor Di and

i Di = D. If D is reduced, so is each Di .

PROOF Since Vi2 ≡ V 2 ≡ f (mod Ui ), the pair (Ui , Vi ) represents a

divisor, so all that needs to be proved is that i Di = D.

Write Ui (x) = j (x ’ aj )cj with aj ∈ Fq . Then

gcd (div(Ui ), div(y ’ Vi )) = cj ([Pj ] ’ [∞]) ,

j

where Pj = (aj , Vj (aj )). But Vi = V + Ui ki for some polynomial ki , so

Vi (aj ) = V (aj ) + Ui (aj )ki (aj ) = V (aj ).

Therefore, the points that appear in the divisors Di for the pairs (Ui , Vi ) are

those that appear in the divisor for (U, V ). The multiplicities of the points

in the sum of the Di add up to those in D since i Ui = U . Therefore,

i Di = D.

The degree of a semi-reduced divisor is the degree of the corresponding

polynomial U . We call a semi-reduced divisor prime if it has degree at least

© 2008 by Taylor & Francis Group, LLC

424 CHAPTER 13 HYPERELLIPTIC CURVES

1, it is de¬ned over Fq , and it cannot be written as a sum of semi-reduced

divisors of smaller degree, each de¬ned over Fq . By the proposition, this is

equivalent to U being an irreducible polynomial in Fq [x].

We say that a semi-reduced divisor is B-smooth if it is the sum of prime

divisors of degree ¤ B.

In the case of elliptic curves, this concept is not useful, since each rational

divisor of degree 0 is in the same divisor class as a 1-smooth divisor. See

Exercise 13.8. However, it turns out to be quite useful for larger g.

Suppose we have divisor classes represented by divisors D1 and D2 , and

we are given that D2 is in the same class as kD1 for some integer k. The

discrete logarithm problem is to ¬nd k.

The ¬rst index calculus attack on the discrete logarithm problem for hy-

perelliptic curves was given by Adleman, DeMarrais, and Huang [3]. Various

re¬nements have been proposed. The variation we present below is essen-

tially due to Harley and Gaudry. Improvements by Th´riault [120] yield an

e

algorithm whose running time is bounded by a constant (depending on the

arbitrarily small number ) times g 5 q 2+ ’(4/(2g+1)) . For g ≥ 3, this is faster

than the square root algorithms when q is large. Therefore, the best curves

for cryptographic applications are probably those with g = 2.

We assume that D1 , D2 are reduced and represented by (Ui , Vi ) for i = 1, 2.

Fix a bound B (often, B = 1). List all the irreducible polynomials T (x) ∈

Fq [x] of degree ¤ B. For each such polynomial T , ¬nd a polynomial W (x)

such that W 2 ≡ f (mod T ), if one exists (see Exercise 13.11). The resulting

list of polynomials (Tj , Wj ), 1 ¤ j ¤ s, is the factor base. Note that we

include only one of (T, W ) and (T, ’W ), since they are inverses of each other

(Exercise 13.5).

Let N = #J(Fq ). We assume that N is known since this is the case in

most cryptographic algorithms. However, there are index calculus methods

that determine N . See [3].

The algorithm proceeds as follows:

1. Start with a “matrix” M with no rows and s columns.

2. Choose random integers m and n.

3. Compute the pair (U, V ) for the sum mD1 + nD2 using Cantor™s algo-

rithm.

4. If U does not factor into irreducible polynomials of degree ¤ B, go back

Tici be the factorization of U into

to Step 2. Otherwise, let U =

irreducible polynomials from the factor base.

5. The factorization in Step 4 yields a decomposition

s

mD1 + nD2 ≡ (±ci )Di (mod principal divisors)

i=1

© 2008 by Taylor & Francis Group, LLC

425

SECTION 13.4 THE DISCRETE LOGARITHM PROBLEM

where Di is the divisor corresponding to (Ti , Wi ) and where +ci is chosen

if Wi ≡ V (mod Ti ) and ’ci is chosen if ’Wi ≡ V (mod Ti ). Append

the row r = (±c1 , . . . , ±cs ) to the matrix M .

6. If the number r of rows of M is less than s, return to Step 2. If r ≥ s,

continue to step 7.

di ri ≡ 0 (mod N )

7. Let ri denote the ith row of M . Find a relation

among the rows of M , with di ∈ Z.

8. Let mi , ni be the values of m, n from Step 2 that yield the row ri . Let

m0 = di mi and n0 = di ni .

9. If gcd(m0 , N ) = 1, let k ≡ ’n0 m’1 (mod N ).

0

10. If gcd(m0 , N ) = 1, continue to do Steps 2 through 9 and ¬nd more rela-

tions among the rows until a relation is found that yields gcd(m0 , N ) =

1.

11. Output k.

REMARK 13.13 What the algorithm does is compute relations

m1 D1 + n1 D2 ≡ c11 D1 + · · · + c1s Ds

··· ··· ···

mr D1 + nr D2 ≡ cr1 D1 + · · · + crs Ds

Adding the appropriate rows corresponding to a relation among the rows

yields

m0 D1 + n0 D2 ≡ 0 · D1 + · · · + 0 · Ds .

Dividing by ’m0 yields D1 ≡ ’(n0 /m0 )D2 .

REMARK 13.14 The Pollard ρ method (Section 5.2.2) also looks at

sums mD1 + nD2 and looks for a match between the divisors obtained for two

di¬erent pairs (m, n). This corresponds to a relation of two rows being equal

in the present method. The possibility of much more general relations among

the rows makes the present method much faster than the ρ method. In the ρ

method, the random integers m, n are chosen by a type of random walk. This

is also a good way to proceed in the present method.

Example 13.5

Consider the curve C : y 2 = x5 ’ 1 over F3 . Let D1 = (x2 ’ 1, x ’ 1) and

D2 = (x2 ’ x ’ 1, ’x + 1). The problem is to ¬nd k such that D2 = kD1 .

© 2008 by Taylor & Francis Group, LLC

426 CHAPTER 13 HYPERELLIPTIC CURVES

Take (x ’ 1, 0) and (x + 1, ’1) as the factor base. Calculations yield

3D1 + 5D2 = ((x + 1)2 , ’x + 1) = 2(x + 1, ’1)

4D1 + 3D2 = (x ’ 1, 0)

D1 + 4D2 = (x2 ’ 1, ’x + 1) = (x ’ 1, 0) + (x + 1, ’1).

If we take (¬rst row) + 2(second row) ’ 2(third row), we obtain

9D1 + 3D2 = 0.

Since the group J(F3 ) has order 10 (see Example 13.4), multiplication by 3

yields

7D1 = D2 .

Exercises

13.1 Let C be the curve in Example 13.4. Use Cantor™s algorithm to show

that (x, i) + (x, ’i) = (1, 0).

13.2 Let E be the elliptic curve y 2 = x3 ’ 2.

(a) Use Cantor™s algorithm to compute the sum of pairs (x ’ 3, 5) +

(x ’ 3, 5).

(b) Compute the sum (3, 5) + (3, 5) on E. Compare with (a). More

generally, see Exercise 13.9 below.

13.3 Let C be the hyperelliptic curve y 2 = x5 ’ 5x3 + 4x + 1.

(a) Show that div(y ’ 1) = [(’1, 1)] + [(’2, 1)] + [(1, 1)] + [(2, 1)] +

[(0, 1)] ’ 5[∞]

(b) Show that div(x) = [(0, 1)] + [(0, ’1)] ’ 2[∞].

(c) Find a reduced divisor equivalent modulo principal divisors to

[(’1, 1)] + [(’1, ’1)] + [(1, 1)] + [(2, 1)] + [(0, 1)] ’ 5[∞].

13.4 (a) Let F (x, y) be a function on a hyperelliptic curve and let G(x, y) =

F (x, ’y). What is the relation between div(F ) and div(G)?

(b) Let D be a principal divisor. Show that w(D) is also a principal

divisor. Give two proofs, one using (a) and the second using the

fact that D + w(D) is principal.

13.5 Let (U, V ) be the pair corresponding to a semi-reduced divisor D. Show

that (U, ’V ) is the pair for w(D).

© 2008 by Taylor & Francis Group, LLC

427

EXERCISES

13.6 Let (U, V ) be the pair corresponding to a semi-reduced divisor.

(a) Use Cantor™s algorithm to show that (U, V ) + (1, 0) = (U, V ).

(b) Use Cantor™s algorithm to show that (U, V ) + (U, ’V ) = (1, 0).

13.7 Let C be a hyperelliptic curve and let D be a divisor of degree 0.

(a) Show that if 3D is principal then 2D is equivalent to w(D) mod

principal divisors.

(b) Let P = ∞ be a point on C. Show that if the genus of C is at least

2 then 3 ([P ] ’ [∞]) is not principal. (Hint: Use the uniqueness

part of Proposition 13.6.)

This shows that the image of C in its Jacobian intersects the 3-

torsion on the Jacobian trivially.

13.8 Let E be an elliptic curve de¬ned over a ¬eld K and let (U, V ) be a pair

of polynomials with coe¬cients in K corresponding to a semi-reduced

divisor class.

(a) Show that the reduction algorithm applied to (U, V ) yields either

the pair (1, 0) or a pair (x ’ a, b), with a, b ∈ K.

(b) Show that (1, 0) corresponds to the divisor 0, and (x ’ a, b) corre-

sponds to the divisor [(a, b)] ’ [∞].

13.9 Let E be an elliptic curve, regarded as a hyperelliptic curve. Show that

Cantor™s algorithm corresponds to addition of points on E by showing

that (x’a1 , b1 )+(x’a2 , b2 ) yields (x’a3 , b3 ), where (a1 , b1 )+(a2 , b2 ) =

(a3 , b3 ).

13.10 Let f1 (T ), . . . , fn (T ) be polynomials (with coe¬cients in some ¬eld K)

that are pairwise without common factors, and let a1 (T ), . . . , an (T ) be

arbitrary polynomials with coe¬cients in K. For each i, let Fi (T ) =

j=i fj . Since gcd(fi , Fi ) = 1, there exists gi (T ) with gi (T )Fi (T ) ≡ 1

(mod fi ) (this can be proved using the Euclidean algorithm). Let

A(T ) = a1 (T )g1 (T )F1 (T ) + · · · + an (T )gn (T )Fn (T ).

Show that A ≡ ai (mod fi ) for all i. (Remark: This is the Chinese

Remainder Theorem for polynomials.)

13.11 Let q be a power of an odd prime. Let U (T ) be an irreducible polynomial

in Fq [T ] of degree n. Then Fq [T ]/(U (T )) is a ¬eld with q n elements.

Let f (T ) ∈ Fq [T ] with f (T ) ≡ 0 (mod U (T )). Show that there exists

n

V (T ) ∈ Fq [T ] such that V 2 ≡ f (mod U ) if and only if f (q ’1)/2 ≡ 1

(mod U ). (Hint: The multiplicative group of a ¬nite ¬eld is cyclic.)

(Remark. There are algorithms for ¬nding square roots in ¬nite ¬elds.

See [25].)

© 2008 by Taylor & Francis Group, LLC