Cryptography Reference
In-Depth Information
(
v
i
+
Then using (
y
−
v
1
)(
y
−
v
2
)
=
F
−
(
v
1
+
v
2
+
H
)
y
+
v
1
v
2
and
u
i
|
Hv
i
−
F
)for
i
=
1
,
2 proves equation (
10.9
).
Finally, it remains to prove that equation (
10.5
) holds. We do this by showing that
v
P
(
v
(
x
)
2
+
H
(
x
)
v
(
x
)
−
F
(
x
))
≥
v
P
(
u
(
x
))
x
P
)
e
for all
P
=
(
x
P
,y
P
)
∈
Supp(
D
). Suppose first that
P
=
ι
(
P
) and that (
x
−
u
3
(
x
).
Then it is sufficient to show that
v
P
(
y
−
v
3
(
x
))
≥
e
. This will follow from equa-
tion (
10.9
). First note that
v
P
(
y
−
v
3
)
=
v
P
((
v
1
+
v
2
+
H
)(
v
3
−
y
)) and that this is at
least min
{
v
P
(
u
3
)
,v
P
((
y
−
v
1
)(
y
−
v
2
))
}
. Then
v
P
(
y
−
v
1
)
+
v
P
(
y
−
v
2
)
≥
v
P
(
u
1
(
x
))
+
v
P
(
u
2
(
x
))
e
.
Now for the case
P
≥
Supp(
D
). Recall that such points only occur in semi-
reduced divisors with multiplicity 1. Since
u
3
(
x
) is of minimal degree we know (
x
=
ι
(
P
)
∈
−
x
P
)
u
3
(
x
). It suffices to show that
v
3
(
x
P
)
=
y
P
, but this follows from equation (
10.8
).
Without loss of generality,
P
∈
Supp(
D
2
) and
P
∈
Supp(
D
1
)(if
P
∈
Supp(
D
i
) for both
i
=
1
,
2 then
P
∈
Supp(
D
)) so (
x
−
x
P
)
s
(
x
),
v
2
(
x
P
)
=
y
P
and (
u
2
/s
)(
x
P
)
=
0. Hence,
v
3
(
x
P
)
=
v
2
(
x
P
)
+
0
=
y
P
.
Let
C
:
y
2
(
x
2
x
5
Exercise
10.3.15
+
+
2
x
+
10)
y
=
+
x
+
1
over
F
11
.Let
D
1
=
+
and
D
2
=
+
(0
,
4)
(6
,
4)
(0
,
4)
(1
,
1).
Determine
the
Mumford
representation
of
D
1
,D
2
,
2
D
1
,D
1
+
D
2
.
We remark that, in practical implementation, one almost always has gcd(
u
1
(
x
)
,u
2
(
x
))
=
1 and so
s
(
x
)
1 and the addition algorithm can be simplified. Indeed, it is possible to give
explicit formulae for the general cases in the addition algorithm for curves of small genus,
we refer to Sections 14.4, 14.5 and 14.6 of [
16
].
=
Exercise 10.3.16
Show that the Cantor addition algorithm for semi-reduced divisors of
degree
m
has complexity
O
(
m
2
M
(log(
q
)) bit operations.
≤
10.3.3 Reduction of divisors in Mumford representation
Suppose we have an affine effective divisor
D
with Mumford representation (
u
(
x
)
,v
(
x
)).
We wish to obtain an equivalent divisor (affine and effective) whose Mumford representation
has deg(
u
(
x
)) of low degree. We will show in Theorem 10.3.21 and Lemma 10.4.6 that one
can ensure deg(
u
(
x
))
≤
g
, where
g
is the genus; we will call such divisors reduced. The
idea is to consider
u
†
(
x
)
monic((
v
(
x
)
2
F
(
x
))
/u
(
x
))
,v
†
(
x
)
H
(
x
)(mod
u
†
(
x
))
(10.10)
=
+
H
(
x
)
v
(
x
)
−
=−
v
(
x
)
−
monic
u
0
+
u
k
x
k
for
u
k
=
where
u
1
x
+···+
0
is
defined
to
be
(
u
0
/u
k
)
+
x
k
. Obtaining (
u
†
(
x
)
,v
†
(
x
)) from (
u
(
x
)
,v
(
x
)) is a
Cantor reduction
step
. This operation appears in the classical reduction theory of binary quadratic forms.
(
u
1
/u
k
)
x
+···+
