Cryptography Reference
In-Depth Information
G
+
(
x
)
is reduced to a polynomial of degree at most
where we mean that v
(
x
)
−
deg(
u
(
x
))
−
1
=
g. Define
monic
v
‡
(
x
)
2
H
(
x
)
v
‡
(
x
)
+
−
F
(
x
)
u
†
(
x
)
=
and
u
(
x
)
v
†
(
x
)
v
‡
(
x
)
H
(
x
)(mod
u
†
(
x
))
.
=−
−
(10.11)
Then
deg(
u
†
(
x
))
≤
g and
2
div(
u
†
(
x
)
,y
v
†
(
x
))
2
div(
u
†
(
x
))
2
div(
u
(
x
)
,y
−
v
(
x
))
∩ A
=
−
∩ A
−
∩ A
v
‡
(
x
))
2
.
+
div(
y
−
∩ A
(10.12)
that
v
‡
(
x
)
so
v
‡
(
x
)
2
H
(
x
)
v
‡
(
x
)
Proof
Note
≡
v
(
x
)(mod
u
(
x
))
and
+
−
F
(
x
)
≡
0
(mod
u
(
x
)); hence,
u
†
(
x
) is a polynomial. The crucial observation is that deg(
v
‡
(
x
))
=
deg(
G
+
(
x
))
1 and so the leading coefficient of
v
‡
(
x
) agrees with that of
G
+
(
x
). Hence, deg(
v
‡
(
x
)
2
=
d
=
g
+
H
(
x
)
v
‡
(
x
)
1 and so deg(
u
†
(
x
))
+
−
F
(
x
))
≤
2
d
−
1
=
2
g
+
≤
2
d
−
1
−
d
=
d
−
1
=
g
as claimed. To show equation (
10.12
) it is sufficient to write
=
l
i
=
1
(
x
u
(
x
)
u
†
(
x
)
x
i
)
e
i
and to note that
−
l
v
‡
(
x
))
2
e
i
(
x
i
,v
‡
(
y
i
))
div(
y
−
∩ A
=
i
=
1
2
div(
u
†
(
x
)
,y
v
†
(
x
))
2
=
−
∩ A
+
+
+
∩ A
div(
u
(
x
)
,y
v
(
x
))
H
(
x
)
and that div(
u
†
(
x
))
div(
u
†
(
x
)
,y
v
†
(
x
))
div(
u
†
(
x
)
,y
v
†
(
x
)
=
−
+
+
+
H
(
x
)).
Let
C
:
y
2
x
6
Example
10.4.7
=
F
(
x
)
=
+
6
=
(
x
−
1)(
x
+
1)(
x
−
2)(
x
+
2)(
x
−
3)
F
7
. Then
G
+
(
x
)
x
3
. Consider the divisor
D
(
x
+
3) over
=
=
(1
,
0)
+
(
−
1
,
0)
+
(2
,
0)
with
Mumford
representation
(
u
(
x
)
,v
(
x
))
=
((
x
−
1)(
x
+
1)(
x
−
2)
,
0).
Performing
gives
u
†
(
x
)
standard
Cantor
reduction
=
F
(
x
)
/u
(
x
)
=
(
x
+
2)(
x
−
3)(
x
+
3),
which
corresponds to the trivial divisor equivalence
D
≡
(
−
2
,
0)
+
(3
,
0)
+
(
−
3
,
0). Instead, we
take
v
‡
=
G
+
(
x
)
G
+
(
x
)(mod
u
(
x
)))
x
3
x
3
u
(
x
). Then
u
†
(
x
)
+
(
−
=
+
(
−
+
u
(
x
))
=
=
monic
(
v
‡
(
x
)
2
F
(
x
))
/u
(
x
)
=
x
2
and
v
†
(
x
)
−
+
5
x
+
2
=
3
x
+
5.
The
divisor
div(
u
†
(
x
)
,y
v
†
(
x
))
2
−
∩ A
is
a
sum
(
P
)
+
(
σ
(
P
))
where
P
∈
C
(
F
7
2
)
−
C
(
F
7
)
and
σ
is the non-trivial element of Gal(
F
7
2
/
F
7
).
(
u
†
(
x
)
,v
†
(
x
)) of equation (
10.11
) is called
composition
and reduction at infinity
; the motivation for this is given in equation (
10.17
) below. Some
authors call it a
baby step
. This operation can be performed even when deg(
u
(
x
))
<d
, and
we analyse it in the general case in Lemma
10.4.14
.
The operation (
u
(
x
)
,v
(
x
))
→
Exercise 10.4.8
Let the notation be as in Lemma
10.4.6
.Let
d
u
=
deg(
u
(
x
)) so that
v
‡
(
x
) agrees with
G
+
(
x
) for the leading
d
deg(
v
‡
(
x
)
2
−
d
u
+
1 coefficients and so
m
=
+