Cryptography Reference
In-Depth Information
consider whether there is a unique such representative of the divisor class. This issue will
be considered in Lemma
10.3.24
below.
Exercise
10.3.12
is relevant for the index calculus algorithms on hyperelliptic curves
and it is convenient to place it here.
Exercise 10.3.12
A semi-reduced divisor
D
defined over
with Mumford representation
(
u
(
x
)
,v
(
x
)) is said to be a
prime divisor
if the polynomial
u
(
x
) is irreducible over
k
.
Show that if
D
is not a prime divisor, then
D
can be efficiently expressed as a sum of
prime divisors by factoring
u
(
x
). More precisely, show that if
u
(
x
)
k
=
u
i
(
x
)
c
i
is the
=
c
i
div(
u
i
(
x
)
,y
complete factorisation of
u
(
x
) over
k
, then
D
−
v
i
(
x
)) where
v
i
(
x
)
=
v
(
x
)mod
u
i
(
x
).
10.3.2 Addition and semi-reduction of divisors in Mumford representation
We now present Cantor's algorithm [
111
]
2
for addition of semi-reduced divisors on a
hyperelliptic curve
C
. As above, we take a purely geometric point of view. An alternative,
and perhaps more natural, interpretation of Cantor's algorithm is multiplication of ideals in
k
(
C
).
Given two semi-reduced divisors
D
1
and
D
2
with Mumford representation (
u
1
(
x
)
,v
1
(
x
))
and (
u
2
(
x
)
,v
2
(
x
)) we want to compute the Mumford representation (
u
3
(
x
)
,v
3
(
x
)) of the
sum
D
1
+
[
x,y
]
⊂ k
D
2
. Note that we are not yet considering reduction of divisors in the divisor
class group. There are two issues that make addition not completely trivial. First, if
P
is
in the support of
D
1
and
ι
(
P
) is in the support of
D
2
then we remove a suitable multiple
of (
P
)
D
2
. Second, we must ensure that the Mumford representation
takes multiplicities into account (i.e., so that equation (
10.5
) holds for (
u
3
(
x
)
,v
3
(
x
))).
+
(
ι
(
P
)) from
D
1
+
(
x
P
,y
P
)on
y
2
Example 10.3.13
Let
P
=
+
H
(
x
)
y
=
F
(
x
) be such that
P
=
ι
(
P
). Let
D
1
=
D
2
=
(
P
) so that
u
1
(
x
)
=
u
2
(
x
)
=
(
x
−
x
P
) and
v
1
(
x
)
=
v
2
(
x
)
=
y
P
. Then
D
1
+
x
P
)
2
and
v
(
x
)
D
2
=
2(
P
). The Mumford repre
s
entation for this divisor has
u
3
(
x
)
=
(
x
−
=
y
P
+
−
∈ k
w
(
x
x
P
)forsome
w
. To satisfy equation (
10.5
) one finds that
y
P
+
x
P
)
2
)
.
2
y
P
w
(
x
−
x
P
)
+
H
(
x
)
y
P
+
wH
(
x
)(
x
−
x
P
)
−
F
(
x
)
≡
0(mod(
x
−
F
(
x
P
)(
x
x
P
)
2
)
Writing
F
(
x
)
≡
F
(
x
P
)
+
−
x
P
)(mod(
x
−
and
H
(
x
)
≡
H
(
x
P
)
+
H
(
x
P
)(
x
x
P
)
2
)gives
−
x
P
)(mod(
x
−
F
(
x
P
)
y
P
H
(
x
P
)
−
w
=
,
2
y
P
+
H
(
x
P
)
which is defined since
P
ι
(
P
).
To help motivate the formula for
v
3
(
x
) in Theorem
10.3.14
we now make some obser-
vations. First, note that the equation
=
1
=
s
1
(
x
)(
x
−
x
P
)
+
s
3
(
x
)(2
y
P
+
H
(
x
))
2
The generalisation of Cantor's algorithm to all hyperelliptic curves was given by Koblitz [
311
].
