Hyperelliptic Curves - Elliptic Curves: Number Theory and Cryptography - page 422

it reduces to the trivial divisor, corresp o nding to the pair (1 , 0). In fact, it is
the divisor of the function x on C .

Koblitz [62] proposed the discrete logarithm problem in groups of the form
J ( F q ) as the basis for cryptosystems such as those in Chapter 6. The first
question is how large is J ( F q )? It was proved by Weil, as a generalization of
Hasse's Theorem, that
( √ q ( √ q +1) 2 g . 1) 2 g

− ≤ # J ( F q ) ≤

Therefore, the “square root” attacks such as Baby Step, Giant Step and the
ρ and λ methods from Chapter 5 work in time around q g/ 2 , which is approx-
imately the square root of the order of the group. However, for Jacobians of
hyperelliptic curves, there is an index calculus that is faster than the square
root algorithms when g 3. (On the other hand, for g = 2, it is possible

that the corresponding cryptosystems are more secure than those for elliptic
curves.) We now describe the method.
Recall that in the index calculus over the integers mod p , we needed the
notions of B -smoothness and of factorization into small primes. The following
result lets us define a similar notion for divisors.

≥

PROPOSITION 13.12
Let ( U, V ) be a pairofpolynom ialsin F q [ x ] representing a sem i-redu ced divi-

sor. F actor U ( x )= i U i ( x ) intopo ynom ialsin F q [ x ] .Let V i ≡ V (mod U i )
with deg V i < deg U i .Then ( U i ,V i ) representsasemi-redu ced divisor D i and

i D i = D .If D is redu ced, so iseach D i .

Since V i ≡ V 2 PROOF ≡ f (mod U i ), the pair ( U i ,V i ) represents a

divisor, so all that needs to be proved is th at i D i = D .

Write U i ( x )= j ( x − a j ) c j with a j ∈ F q .Then

V i )) =
j

gcd (div( U i ) , div( y − c j ([ P j ] − [ ∞ ]) ,

where P j =( a j ,V j ( a j )). But V i = V + U i k i for some polynomial k i ,so

V i ( a j )= V ( a j )+ U i ( a j ) k i ( a j )= V ( a j ) .

Therefore, the points that appear in the divisors D i for the pairs ( U i ,V i )are
those that appear in the divisor for ( U, V ). The multiplicities of the points

in the sum of the D i adduptothosein D since i U i = U .

Therefore,

i D i = D .

The degree of a semi-reduced divisor is the degree of the corresponding
polynomial U . We call a semi-reduced divisor prime if it has degree at least