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

1, it is defined over F q , and it cannot be written as a sum of semi-reduced
divisors of smaller degree, each defined over F q . By the proposition, this is
equivalent to U being an irreducible polynomial in F q [ x ].
We say that a semi-reduced divisor is B - smooth if it is the sum of prime
divisors of degree ≤ B .
In the case of elliptic curves, this concept is not useful, since each rational
divisor of degree 0 is in the same divisor class as a 1-smooth divisor. See
Exercise 13.8. However, it turns out to be quite useful for larger g .
Suppose we have divisor classes represented by divisors D 1 and D 2 ,and
we are given that D 2 is in the same class as kD 1 for some integer k .The
discrete logarithm problem is to find k .
The first index calculus attack on the discrete logarithm problem for hy-
perelliptic curves was given by Adleman, DeMarrais, and Huang [3]. Various
refinements have been proposed. The variation we present below is essen-
tially due to Harley and Gaudry. Improvements by Theriault [120] yield an
algorithm whose running time is bounded by a constant (depending on the
arbitrarily small number )times g 5 q 2+ − (4 / (2 g +1)) .For g ≥ 3, this is faster
than the square root algorithms when q is large. Therefore, the best curves
for cryptographic applications are probably those with g =2.
We assume that D 1 ,D 2 are reduced and represented by ( U i ,V i )for i =1 , 2.
Fix a bound B (often, B = 1). List all the irreducible polynomials T ( x )

∈

F q [ x ]ofdegree ≤ B . For each such polynomial T , find a polynomial W ( x )

such that W 2

≡ f (mod T ), if one exists (see Exercise 13.11). The resulting
list of polynomials ( T j ,W j ) , 1 ≤ j ≤ s ,isthe factor base . Note that we
include only one of ( T,W )and( T,−W ), since they are inverses of each other
(Exercise 13.5).
Let N =# J ( F q ). We assume that N is known since this is the case in
most cryptographic algorithms. However, there are index calculus methods
that determine N . See [3].
The algorithm proceeds as follows:

1. Start with a “matrix” M with no rows and s columns.

2. Choose random integers m and n .

3. Compute the pair ( U, V )forthesum mD 1 + nD 2 using Cantor's algo-
rithm.

4. If U does not factor into irreducible polynomials of degree ≤ B ,goback

to Step 2. Otherwise, let U = T c i i be the factorization of U into
irreducible polynomials from the factor base.

5. The factorization in Step 4 yields a decomposition

s

mD 1 + nD 2 ≡ ( ± c i ) D i (mod principal divisors)

i =1