Cryptography Reference
In-Depth Information
Example 10.3.4 Let P 1 =
( x 1 ,y 1 ) and P 2 =
( x 2 ,y 2 ) be points on a hyperelliptic curve C
such that x 1 =
x 2 .Let D
=−
( P 1 )
+
2( P 2 )
+
( ι ( P 2 )). Then D is not semi-reduced. One has
D
+
div( x
x 1 )
=
D
+
( P 1 )
+
( ι ( P 1 ))
=
( ι ( P 1 ))
+
2( P 2 )
+
( ι ( P 2 )) ,
which is still not semi-reduced. Subtracting div( x
x 2 ) from the above gives
D
+
div(( x
x 1 ) / ( x
x 2 ))
=
( ι ( P 1 ))
+
( P 2 ) ,
which is semi-reduced.
10.3.1 Mumford representation of semi-reduced divisors
Mumford [ 399 ] introduced 1 a representation for semi-reduced divisors. The condition that
the divisor is semi-reduced is crucial: if points P
( x P ,y P ) and ( x P ,y P ) with y P =
y P
=
both appear in the support of the divisor then no polynomial v ( x ) can satisfy both v ( x P )
=
y P .
y P and v ( x P )
=
= l i = 1 e i ( x i ,y i ) be a non-zero semi-reduced divisor on a hyperel-
Lemma 10.3.5 Let D
liptic curve C : y 2
+
H ( x ) y
=
F ( x ) (hence, D is affine and effective). Define
l
x i ) e i
u ( x )
=
( x
∈ k
[ x ] .
i = 1
Then there is a unique polynomial v ( x )
∈ k
[ x ] such that deg( v ( x )) < deg( u ( x )) , v ( x i )
=
y i
for all 1
i
l, and
v ( x ) 2
+
H ( x ) v ( x )
F ( x )
0(mod u ( x )) .
(10.5)
In particular, v ( x )
=
0 if and only if u ( x )
|
F ( x ) .
=
Proof Since D is semi-reduced there is no conflict in satisfying the condition v ( x i )
y i .
If all e i =
1 then the result is trivial. For each i such that e i > 1 write v ( x )
=
y i +
( x
x i ) W ( x ) for some polynomial W ( x ). We compute v ( x )(mod( x
x i ) e i ) so it satisfies
v ( x ) 2
x i ) e i ) by Hensel lifting (see Section 2.13 )as
+
H ( x ) v ( x )
F ( x )
0(mod( x
follows: if v ( x ) 2
x i ) j G j ( x ) then set v ( x )
+
H ( x ) v ( x )
F ( x )
=
( x
=
v ( x )
+
w ( x
x i ) j where w is an indeterminate and note that
v ( x ) 2
H ( x ) v ( x )
x i ) j ( G j ( x )
x i ) j + 1 ) .
+
F ( x )
( x
+
2 v ( x ) w
+
H ( x ) w )(mod( x
It suffices to find w such that this is zero, in other words, solve G j ( x i )
+
w (2 y i +
H ( x i ))
=
0. Since D is semi-reduced, we know 2 y i +
H ( x i )
=
0 (since P
=
ι ( P ) implies n P =
1).
The result follows by the Chinese remainder theorem.
1
Mumford remarks on pages 3-17 of [ 399 ] that a special case of these polynomials arises in the work of Jacobi. However, Jacobi
only gives a representation for semi-reduced divisors with g points in their support, rather than arbitrary semi-reduced divisors.
 
Search WWH ::




Custom Search