Chapter 13
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 , 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 , 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,
), 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  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  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 . Various
reп¬Ѓnements have been proposed. The variation we present below is essen-
tially due to Harley and Gaudry. Improvements by ThВґriault  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 .
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 .)

В© 2008 by Taylor & Francis Group, LLC