Cryptography Reference
In-Depth Information
10.4.1 Addition of divisor classes on ramified models
On a hyperelliptic curve with ramified model there is only a single point at infinity. We will
show in this section that, for such curves, one can compute in the divisor class group using
only affine divisors.
We use the Cantor algorithms for addition, semi-reduction and reduction. In general,
if one has a semi-reduced divisor D then, by case 1 of Lemma 10.3.20 , a reduction step
reduces the degree of D by 2. Hence, at most deg( D ) / 2 reduction steps are possible.
Theorem 10.4.1 Let C be a hyperelliptic curve with ramified model. Then every degree
zero divisor class on C has a unique representative of the form D
n (
) where D is
semi-reduced and where 0
n
g.
Proof Theorem 10.3.21 showed that every affine divisor is equivalent to a semi-reduced
divisor D such that 0
deg( D )
g . This corresponds to the degree zero divisor D
n (
)
where n
=
deg( D ). Uniqueness was proved in Lemma 10.3.24 .
A degree zero divisor of the form D
n (
) where D is a semi-reduced divisor of
degree n and 0
g is called reduced . We represent D using Mumford representation
as ( u ( x ) ,v ( x )) and we know that the polynomials u ( x ) and v ( x ) are unique. The divisor
class is defined over
n
[ x ].
Addition of divisors is performed using Cantor's composition and reduction algorithms as
above.
k
if and only if the corresponding polynomials u ( x ) ,v ( x )
∈ k
Exercise 10.4.2 Let C : y 2
+
H ( x ) y
=
F ( x ) be a ramified model of a hyperelliptic curve
over
F q . Show that the inverse (also called the negative) of a divisor class on C represented
as ( u ( x ) ,v ( x )) is ( u ( x ) ,
v ( x )
( H ( x )(mod u ( x )))).
Exercise 10.4.3 Let C be a hyperelliptic curve over
of genus g with ramified model.
Let D 1 and D 2 be reduced divisors on C . Show that one can compute a reduced divisor
representing D 1 +
k
D 2 in O ( g 3 ) operations in
k
. Show that one can compute [ n ] D 1 in
O (log( n ) g 3 ) operations in
k
(here [ n ] D 1 means the n -fold addition D 1 +
D 1 +···+
D 1 ).
=
When the genus is 2 (i.e., d
3) and one adds two reduced divisors (i.e., effective
divisors of degree
2) then the sum is an effective divisor of degree at most 4 and so only
one reduction operation is needed to compute the reduced divisor. Similarly, for curves
of any genus, at most one reduction operation is needed to compute a reduced divisor
equivalent to D
( P ) where D is a reduced divisor (such ideas were used by Katagi,
Akishita, Kitamura and Takagi [ 299 , 298 ] to speed up cryptosystems using hyperelliptic
curves).
For larger genus there are several variants of the divisor reduction algorithm. In Section 4
of [ 111 ], Cantor gives a method that uses higher degree polynomials than y
+
v ( x ) and
requires fewer reduction steps. In Section VII.2.1 of [ 61 ], Gaudry presents a reduction
algorithm, essentially due to Lagrange, that is useful when g
3. The NUCOMP algorithm
(originally proposed by Shanks in the number field setting) is another useful alternative.
Search WWH ::




Custom Search