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
=
+
Search WWH ::




Custom Search