On the discrete logarithm problem in class groups of curves

Claus Diem

August 17, 2010

Abstract

We study the discrete logarithm problem in degree 0 class groups of curves over finite fields, with particular emphasis on curves of small genus. We prove that for every fixed g ≥ 2, the discrete logarithm problem in degree 0 class groups of curves of genus g can be solved in an expected time of Õ(q^{2− \frac{2}{g}}), where 𝔽_{q} is the ground field. This result generalizes a corresponding result for hyperelliptic curves given in imaginary quadratic representation with cyclic degree 0 class group, and just as this previous result, it is obtained via an index calculus algorithm with double large prime variation.

Generalizing this result, we prove that for fixed g_{0} ≥ 2 the discrete logarithm problem in class groups of all curves C/𝔽_{q} of genus g ≥ g_{0} can be solved in an expected time of Õ((q^{g})^{\frac{2}{g_{0}} (1− \frac{1}{g_{0}} )}) and in an expected time of Õ(# Cl^{0}(C)^{\frac{2}{g_{0}} (1− \frac{1}{g_{0}} )}).

As a complementary result we prove that for any fixed n ∈ ℕ with n ≥ 2 the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}}, q a prime power, can be solved in an expected time of Õ(q^{2− \frac{2}{n}}).

Furthermore, we give an algorithm for the efficient construction of a uniformly randomly distributed effective divisor of a specific degree, given the curve and its L-polynomial.

Contents

1 Introduction 2

2 Representations and basic computations 4

3 Index calculus for curves of fixed genus 11 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 The index calculus algorithm . . . . . . . . . . . . . . . . . . 13 3.3 Analysis of the index calculus algorithm . . . . . . . . . . . . 18 3.4 On the number of special divisors . . . . . . . . . . . . . . . . 23 3.5 Finding a generating system . . . . . . . . . . . . . . . . . . . 25

4 Index calculus for curves of lower-bounded genus 33 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5 Index calculus for elliptic curves over extension fields of a fixed degree 36 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 The decomposition algorithm . . . . . . . . . . . . . . . . . . 37 5.3 The index calculus algorithm . . . . . . . . . . . . . . . . . . 40

References 42

1 Introduction

With a deterministic algorithm, one can solve the discrete logarithm problem in degree 0 class groups of curves C/𝔽_{q} in a time of Õ(# Cl^{0}(C)^{\frac{1}{2}} ).^{1}

This work is motivated by the following question: Under which conditions on the genera of the curves can one solve the discrete logarithm problem in degree 0 class groups of curves in an expected time of o(# Cl^{0}(C)^{\frac{1}{2}} )? The underlying model of computation is here and throughout this work a randomized random access machine model with commands as in [AHU74] and an additional command to choose 0 or 1 uniformly at random. The running time is then determined with the logarithmic cost function.

We show that the condition that the genus be ≥ 3 is sufficient. Indeed, we prove that under this condition the discrete logarithm problem can be solved in an expected time of Õ(# Cl^{0}(C)^{\frac{4}{9}} ). It is also natural to bound running times in terms of g^{g}, where g is the genus. Again we prove that under the condition that the genus be ≥ 3 one can obtain an expected running time of Õ((q^{g})^{\frac{4}{9}} ).

1This result follows with the baby-step-giant-step algorithm combined with a precomputation. It is based on a particular representation of the input curve and input divisor classes which is described at the end of Section 2.

Our main contribution is the following theorem.

Theorem 1 Let some natural number g ≥ 2 be fixed. Then the discrete logarithm problem in the degree 0 class groups of curves of genus g over finite fields can be solved in an expected time of

Õ(q^{2− \frac{2}{g}}) ,

where 𝔽_{q} is the ground field of the curve.

The algorithms for this theorem have storage requirements of Õ(q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ). More concretely, although the algorithms are randomized, there exists a function in Õ(q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ) such that the storage requirements are bounded by this function for every run.

This theorem is obtained via index calculus algorithms with double large prime variation. A corresponding result for hyperelliptic curves in imaginary quadratic representation and with cyclic degree 0 class groups was obtained in [GTTD07], and on a heuristic basis an obvious generalization of the algorithm for the theorem in [GTTD07] already gives rise to the result in Theorem 1. A related work is [Nag07], in which a similar algorithm is given. We note however that the main “theorem” in [Nag07] is not proven but only established on a heuristic basis.

The algorithms in both works are also based on the index calculus method, and both follow the “double large prime variation strategy”. The algorithm presented in this work is quite closely related to – albeit different from – the algorithm in [Nag07].

From Theorem 1 and results in [Heß05], the following theorem follows quite easily.

Theorem 2 Let some natural number g_{0} ≥ 2 be fixed. Then the discrete logarithm problem in the degree 0 class groups of curves C/𝔽_{q} of genus g ≥ g_{0} can be solved in an expected time of

Õ((# Cl^{0}(C))^{\frac{2}{g_{0}} (1− \frac{1}{g_{0}} )})

as well as in an expected time of

Õ((q^{g})^{\frac{2}{g_{0}} (1− \frac{1}{g_{0}} )}) .

As a complementary result to Theorem 1, we prove the following theorem on the elliptic curve discrete logarithm problem over extension fields.

Theorem 3 Let some natural number n ≥ 2 be fixed. Then the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}}, q a prime power, be solved in an expected time of

Õ(q^{2− \frac{2}{n}}) .

The algorithms for this theorem are similar to the one for Theorem 1. The key difference is that we now generate relations by solving systems of polynomial equations over 𝔽_{q}, in contrast to factoring divisors.

Again on a heuristic basis, the result in Theorem 3 was already established in [Gau09] with a similar algorithm.

Overview

We now give an overview on the rest of this work. In the next section we discuss how we represent curves, divisors and divisor classes. At the end of the section we indicate how the input data to the algorithms are represented, and we discuss the representation of divisor classes by unique bit strings. Note that unique representation of group elements is crucial for the babystep-giant-step algorithm and thus for the result mentioned at the beginning of this work. In Section 3 we give the algorithm for Theorem 1. For this we first give an algorithm which operates well if applied to an instance as in Theorem 1 together with a generating system, and we give an algorithm which with a high probability outputs such a generating system. We show how these two algorithms can be combined in such a way that Theorem 1 follows. Building on Theorem 1, in Section 4 we give an algorithm for Theorem 2. In Section 5 we show how the algorithm for Theorem 1 can be modified in such a way that one obtains Theorem 3. This modification as well as the analysis of the algorithm rely crucially on algorithms and results in [Die10].

Acknowledgments

I thank Wulf-Dieter Geyer and Florian Heß for discussions on representations of divisors and Ralf Gerkmann and Alan Lauder for discussions on point counting algorithms. I thank Peter Bruin for pointing out a mistake in the algorithm for the computation of uniformly randomly distributed effective divisor of a specific degree.

2 Representations and basic computations

In this section we describe how we represent the basic objects of our computation via bit strings: Curves (always assumed to be smooth, proper and geometrically irreducible) over finite fields and divisors and divisor classes on such curves. We also discuss basic computations with these objects. We fix some notation as we go along.

For the representation of divisors we follow an ideal and function field theoretic approach which is inspired the by number field theoretic analog. This approach is convenient for several reasons. First, one can easily adapt the usual algorithms for arithmetic with ideals in number fields (as for example in [Coh96]) to the function field theoretic setting. Second, using the ideal theoretic approach an efficient and simple algorithm for the computation of Riemann-Roch spaces L(D) can be given ([Heß01]). The following exposition is heavily inspired by [Heß01]. Further information, including proofs of all claims, can be found in [Die08, Chapter 2].

Let k be a field. Then we define 𝔸_{k}^{1} := Spec(k[x]) and ℙ_{k}^{1} := Proj(k[X, Y]); we identify k[x] with k[\frac{X}{Y}] ⊂ k(ℙ^{1}) via x ⟷ \frac{X}{Y}, and we define ∞ := (0 : 1) ∈ ℙ^{1}(k). We obtain a canonical inclusion 𝔸_{k}^{1} ↪ ℙ_{k}^{1} and with this inclusion a decomposition ℙ^{1}(\overline{k}) = 𝔸^{1}(\overline{k}) ˙∪ \{∞\}. Furthermore we set ℙ_{k}^{2} := Proj(k[X, Y, Z]).

By a curve over k we mean a smooth, proper and geometrically irreducible 1-dimensional k-scheme.

Curves

In the following, q is always the power of a prime p, and we set k := 𝔽_{q}.

We represent curves via plane models: Let C/k be a curve. Then by a plane model of C we mean a 1-dimensional closed subscheme C_{pm} of ℙ_{k}^{2} which is birational to C. We represent such a plane model C_{pm} by a defining homogeneous polynomial F (X, Y, Z). Note that the degree of C_{pm} equals the degree of F; we denote this degree by d. Furthermore, we denote the genus of C by g.

The following proposition is [Heß01, Theorem 56].

Proposition 2.1 Every curve over a finite field has a plane model of degree O(g) (uniformly over all finite fields).

Let us now fix a curve C of genus ≥ 1 with a birational morphism to a plane model: π : C ⟶ C_{pm}.

We set x := \frac{X}{Z} , y := \frac{Y}{Z} and f(x, y) := \frac{F (X,Y,Z)}{Z^{d}}, and we denote the induced functions on C also by x, y. We assume that the covering x : C ⟶ ℙ_{k}^{1} is separable (otherwise the covering y is separable and we can interchange x and y), and we set r := deg(x) = [k(C) : k(x)].

Divisors

We now come to closed points and divisors. For this, we consider the subrings (x_{∗}O_{C})(𝔸_{k}^{1}) and (x_{∗}O_{C})_{∞} of k(C); these rings are the integral closures of k[x] and k[\frac{1}{x}]_{( \frac{1}{x} )} in k(C). They are called finite and infinite order of k(C) (with respect to x).

Now the closed points of C correspond to the places of k(C), and these in turn correspond to maximal ideals of (x_{∗}O_{C})(𝔸_{k}^{1}) as well as (x_{∗}O_{C})_{∞}.

The main idea for the ideal representation of points is to fix bases of these orders and to represent the points of C by “nice” k[x]- respectively k[\frac{1}{x}]_{( \frac{1}{x} )}- bases of the corresponding maximal ideals. In order to have a better control over the size of this representation, we consider however prime ideals of (x_{∗}O_{C})(\frac{1}{x}(𝔸_{k}^{1})) with support “at infinity” instead of prime ideals in (x_{∗}O_{C})_{∞}.

Now divisors can be represented in two ways: The first way is to take the representation of points as a basis for what is called a free representation: The divisors are represented by their support and the coefficient vector, and the points are represented by maximal ideals of the two orders.

Another way to represent divisors is to consider the isomorphisms

Div(C) ˜ ⟶ Div((x_{∗}O_{C})(𝔸_{k}^{1})) × Div((x_{∗}O_{C})_{∞})
˜ ⟶I((x_{∗}O_{C})(𝔸_{k}^{1})) × I((x_{∗}O_{C})_{∞}) ,

(1)

where the first isomorphism is induced by pull-back and the second isomorphism is induced by the canonical isomorphisms between the divisor and ideal groups. Via these isomorphisms every divisor corresponds to a pair of fractional ideals, a “finite” and an “infinite” fractional ideal. To represent the “infinite” fractional ideal, one furthermore applies the canonical inclusion I((x_{∗}O_{C})_{∞}) ↪ I((x_{∗}O_{C})(\frac{1}{x}(𝔸_{k}^{1}))). We call this representation of divisors the joint ideal representation.

Notation 2.2 Let D be a divisor on C. Then the associated “finite” fractional ideal in I((x_{∗}O_{C})(𝔸_{k}^{1})) is denoted by I^{fin}(D). The associated “infinite” fractional ideal in I((x_{∗}O_{C})(\frac{1}{x}(𝔸_{k}^{1}))) is denoted by I^{∞}(D), and the corresponding ideal in I((x_{∗}O_{C})_{∞}) (the localization of I^{∞}(D) at ∞) by (I^{∞}(D))_{∞}.

Note here that I^{∞}(D) by definition only has support “at infinity”, and (I^{∞}(D))_{∞} is the ideal generated by I^{∞}(D) inside (x_{∗}O_{C})_{∞}.

We now need to describe how we represent the fractional ideals of the orders (x_{∗}O_{C})(𝔸_{k}^{1}) and ((x_{∗}O_{C})(\frac{1}{x}(𝔸_{k}^{1})).

Let f(x, y) = ∑_{i=0}^{r} a_{i}(x) y^{i}. Let ã_{i}(x) := a_{i}(x) a_{r}^{r−i−1}(x) for i = 0, …, r, ỹ := a_{r}(x) y ∈ k(C) and ˜ ỹ := \frac{ỹ}{x^{c}} ∈ k(C) with c := max\{⌈\frac{deg(ã_{i}(x))}{r−i}⌉ | 0 ≤ i ≤ r\}. Then ỹ is integral over k[x] as it is a root of the monic polynomial ∑_{i=0}^{r} ã_{i}(x) · t^{i} ∈ k[x][t] and ˜ ỹ is integral over k[\frac{1}{x}] as it is a root of the monic polynomial ∑_{i=0}^{r} \frac{ã_{i}(x)}{x^{c(r−i)}} · t^{i} ∈ k[\frac{1}{x}][t].

Now let w_{1}, …, w_{r} be the HNF-basis (HNF = Hermite normal form) of (x_{∗}O_{C})(𝔸_{k}^{1}) with respect to 1, ỹ, …, ỹ^{r−1}. Then we represent a fractional ideal of (x_{∗}O_{C})(𝔸_{k}^{1}) by the coordinate vectors of its HNF-basis with respect to w_{1}, …, w_{r}.

We proceed similarly with the “infinite order”, substituting ỹ by ˜ ỹ. We remark that one can compute the HNF-basis of (x_{∗}O_{C})(𝔸_{k}^{1}) (deter-

ministically) in a time which is polynomially bounded in d · log(q), following ideas by Zassenhaus and by Grauert and Remmert.

The input to all algorithms for the following computations with divisors and divisor classes consists of a curve, represented by a plane model, together with HNF-bases for the two orders and some additional data.

Inspired by [Heß01] we define:

Definition 2.3 Let D be a divisor on C, and let D_{+} be the “positive part” and D_{−} be the “negative part of D (such that D_{+}, D_{−} ≥ 0, D_{+} and D_{−} have disjoint support and D = D_{+} −D_{−}). Then the height of D is ht(D) := max{deg(D_{+}), deg(D_{−})}.

Now basic divisor arithmetic (addition and inversion) in both free as well as joint ideal representation can be performed in a time which is polynomially bounded in d · h · log(q), where h is the maximum of the heights of the divisors involved.

By this result it is obvious that given a divisor D in free ideal representation, one can compute (deterministically) the corresponding divisor in joint ideal representation in a time which is polynomially bounded in d · ht(D) · log(q). The opposite computation is possible with a randomized algorithm whose expected running time is polynomially bounded in d · ht(D) · log(q). The randomization is only required to factorize polynomials over finite fields. By using Berlekamp’s absolute algorithm for this task, one then obtains a deterministic algorithm with a running time of p·(d·ht(D)·log(q))^{O(1)}, where – as indicated above – p is the characteristic.

For arithmetic in degree 0 class groups the computation of Riemann-Roch spaces L(D) for a divisor D is crucial. An efficient and simple algorithm using the ideal theoretic representation given here was presented by Heß in [Heß01]. It relies on the equality

L(D) = I^{fin}(−D) ∩ I^{∞}(−D)_{∞}

and computes this intersection with a reduction algorithm. In short, one computes a k[x]-basis v_{1}, …, v_{r} of I^{fin}(−D) and integers d_{1}, …, d_{r} such that x^{d_{1}}v_{1}, …, x^{d_{r}}v_{r} is a k[\frac{1}{x}]_{( \frac{1}{x} )}-basis of I^{∞}(−D)_{∞}. A k-basis of L(D) can then easily be deduced. For the computation one considers the coordinate matrix of some k[x]-basis of I^{fin}(−D) with respect to a k[\frac{1}{x}]_{( \frac{1}{x} )}-basis of I^{∞}(−D)_{∞} and applies a reduction algorithm on this matrix. The computation can be performed in a time which is polynomially bounded in d · ht(D) · log(q).

Also, given a function f ∈ k(C)^{∗}, one can compute the associated principal divisor in a time which is polynomially bounded in d · deg(f) · log(q).

Divisors over extension fields

Let still k := 𝔽_{q}, let K := 𝔽_{q^{n}} with some natural number n, and let C′ be a curve over K. Let C′ again be given by a plane model in ℙ_{K}^{2}, as above. Then there are several obvious possibilities to represent ideals of (x_{∗}O_{C})(𝔸_{K}^{1}).

First, one can proceed as above over K, yielding the usual joint and free representations. Second, one can proceed analogously to the above but starting from the (not geometrically irreducible) scheme C′ over k (corresponding to the function field K(C′)|k).

Let now C again be a curve over k, represented by a plane model. Let C′ := C_{K}, and let α_{1}, …, α_{n} be a k-basis of K. Then there is a third possibility to represent divisors: Let w_{1}, …, w_{r} be as above. Then the elements α_{i}w_{j} for i = 1, …, n and j = 1, …, r form a k[x]-basis of (x_{∗}O_{C′})(𝔸_{K}^{1}), and one can represent fractional ideals of (x_{∗}O_{C′})(𝔸_{K}^{1}) via HNF-bases with respect to this basis.

Of course these considerations also apply to the “infinite ideals” and give several possibilities to represent divisors on C′.

One can show that one can change between the two or three joint representations in a time which is polynomially bounded in d · ht(D) · log(q).

Let now again C′ = C_{K}, let α_{1}, …, α_{n} be a k-basis of K with α_{1} = 1, and let an ideal I of (x_{∗}O_{C})(𝔸_{K}^{1}) be given in joint or free representation as described above. Then one immediately obtains the intersection of I with k(C), again in joint or free representation. In particular, given a divisor D on C′ in free representation, one can compute its norm with respect to the covering C′ ⟶ C in a time which is polynomially bounded in d·ht(D)·log(q).

Divisor classes

Let us recall the following definition (see [Heß01]):

Definition 2.4 Let D_{0} be a divisor on C of degree ≥ 1, and let D̃ be an effective divisor on C. Then D̃ is (maximally) reduced along D_{0} if the linear system |D̃ − D_{0}| is empty.

Let now D be any divisor on C, and let D̃ be an effective divisor reduced along D_{0} such that D ∼ D̃ + rD_{0} for some r ∈ ℤ. Then D̃ is called a reduction of D along D_{0}.

One can easily see that the set of reductions of D along D_{0} form a complete linear system. Moreover, if D_{0} is a k-rational point of C then the reduction is unique.

Remark 2.5 It does not suffice that D_{0} has degree 1 (without the condition of being effective) in order that the reduction be unique. Here is a counterexample.

Let C be a hyperelliptic curve with a k-rational point P which is not a Weierstraß point. Let D̃ := P + ι(P) and let D_{0} := 2 ι(P) − P, where ι is the hyperelliptic involution. Then D̃ −D_{0} = 2P −ι(P), which is not linearly equivalent to a point. Thus D̃ is reduced along D_{0}, but |D̃| has dimension 1.

To represent divisor classes, we fix a divisor D_{0} of degree ≥ 1 and represent a class a by a corresponding reduced divisor and the degree of a. For computational purposes one can for example define D_{0} as the canonical divisor div(dx). With the formula

div(dx) = −2(x)_{−} + R ,

where R is the ramification divisor of x : C ⟶ ℙ_{k}^{1}, this divisor can be computed in a time which is polynomially bounded in d · log(q). Generally, if the height of D_{0} is polynomially bounded in d, then the arithmetic in Cl^{0}(C) can be performed in a time which is polynomially bounded in d·log(q), provided divisors are represented in joint ideal representation. For the free representation, the computation can be performed in an expected time which is polynomially bounded in d · log(q).

Note that there always exists a divisor of degree 1 on C. In fact, by the Hasse-Weil bound, for every m ≥ ⌈2 log_{q}(2g)⌉, there is a 𝔽_{q^{m}}-rational point on C and thus a closed point on C whose degree divides m (cf. [Heß05, Proposition 32]). One can compute two closed points with degrees dividing ⌈2 log_{q}(2g)⌉ and ⌈2 log_{q}(2g)⌉ + 1 in an expected time which is polynomially bounded in d·log(q). These then give rise to a divisor of height ⌈2 log_{q}(2g)⌉+ 1 and degree 1.

For fixed genus g, one can easily determine if there exists a k-rational point on C and if so compute such a point in an expected time which is polynomially bounded in log(q). If one defines D_{0} as such a point, then – as already mentioned – the representation of degree 0 divisor classes by reduced divisors is unique. In the algorithm for Theorem 1 we employ such a representation.

Let us finally consider the important case that d is polynomially bounded in g. Then in the statements above d · log(q) can of course be substituted by g · log(q). Moreover, as shown in [LMD90], one has

# Cl^{0}(C) ≥ \frac{(q − 1)^{2}}{(q + 1) · q} · \frac{1}{g + 1} · q^{g} ≥ \frac{1}{6} · \frac{1}{g + 1} · q^{g} ,  (2)

and this implies that d·log(q) can then also be substituted by log(# Cl^{0}(C)). In particular if the degree of the divisor D_{0} is also polynomially bounded in g, the arithmetic in the degree 0 class group can then be performed in a time which is polynomially bounded in log(# Cl^{0}(C)).

Representation of input data

We can now describe how the input data in the algorithms for the theorems are represented.

The curve is always given by a plane model of degree O(g); in Theorem 1 it is therefore given by a plane model of bounded degree. We fix a divisor D_{0} of degree 1 and height O(g), and we represent divisor classes by along D_{0} reduced divisors. The divisors in turn are given in free or joint ideal representation as described above.

Unique representation and generic algorithms

For some purposes, for example for the baby-step-giant-step algorithm, one requires a unique representation of elements of Cl^{0}(C) by bit strings.

One possibility to achieve this is to consider a constant field extension such that the curve has a rational point. For example, as mentioned above, with m := ⌈2 log_{q}(2g)⌉, the curve C_{𝔽_{q^{m}}} has a 𝔽_{q^{m}}-rational point, and with a randomized algorithm, one can compute such a point P_{0} in an expected time which is polynomially bounded in d · log(q). All elements of Cl^{0}(C_{𝔽_{q^{m}}}), thus in particular those of the subgroup Cl^{0}(C), can then uniquely be represented by along P_{0} reduced divisors.

Given an instance of the discrete logarithm problem as described above, we would like to compute the discrete logarithm deterministically in a time of Õ(# Cl^{0}(C)^{\frac{1}{2}} ).

In the case of genus 1 curves, D_{0} is linearly equivalent to a unique 𝔽_{q}- rational point P_{0}. One can therefore apply the baby-step-giant-step algorithm directly, and one obtains the desired result.

We therefore consider the case that the genus is ≥ 2. Again, let p be the characteristic. In this case we first compute a field extension λ|𝔽_{q} of degree ≤ ht(D_{0}) and a λ-rational point P_{0} on C_{λ}. Here the field extension is represented by a multiplication table. We then represent divisor classes by along P_{0} reduced divisors and again apply the baby-step-giant-step algorithm. The baby-step giant step algorithm has a running time of Õ(# Cl^{0}(C)^{\frac{1}{2}} ), and we have to show that the computation of λ and P_{0} can be performed (deterministically) in this time as well.

For this, we proceed as follows: First we compute the free representation of D_{0}, and we fix a prime divisor E occurring in D_{0}. As mentioned above, this can be achieved deterministically in a time of p·(g·log(q))^{O(1)}. Note also that deg(E) ≤ ht(D_{0}) ∈ O(g). Assume now that E corresponds to a “finite” ideal, that is, to an ideal in (x_{∗}O_{C})(𝔸_{𝔽_{q}}^{1}) (the other case is similar); let 𝔭 be this ideal. An HNF-basis for 𝔭 easily gives an 𝔽_{q} basis of (x_{∗}O_{C})(𝔸_{λ}^{1})/𝔭 and a multiplication table; let λ be this field. Then E as a divisor on C_{λ} splits completely. So we compute the free representation of E as a divisor of C_{λ} and fix one of the points occurring in it. This can again be achieved (deterministically) in a time of p · (g · log(q))^{O(1)}.

We remark that for genus 1 curves over prime fields the assumption that D_{0} has degree 1 is crucial. If we drop this assumption, we do not know how to perform the computation (deterministically) in the desired time.

3 Index calculus for curves of fixed genus

3.1 Overview

In this section we present an index calculus algorithm with double large prime variation for curves of a fixed genus g ≥ 2, leading to Theorem 1.

The input of the algorithm consists of a tuple (C/𝔽_{q}, a, b), where C is a curve of genus g over 𝔽_{q}, a, b ∈ Cl^{0}(C) and b ∈ ⟨a⟩. The representation of the input follows the description given in the previous section: The curve is represented by a plane model, a divisor D_{0} of degree 1 is fixed and a, b are represented by along D_{0} reduced divisors which in turn is given in free or joint ideal representation as described above. Here the degree of the plane model as well as the height of D_{0} are bounded by some constant.

We now give an outline of the proof of Theorem 1.

First we give an index calculus algorithm with double large prime variation which gives rise to the following proposition.

Proposition 3.1 Let us fix some g ≥ 2. Then there exists a randomized algorithm such that the following holds: Upon input of a curve C/𝔽_{q} of genus g, elements a, b ∈ Cl^{0}(C) with b ∈ ⟨a⟩ and a system c_{1}, …, c_{u} of elements of Cl^{0}(C), if the algorithm terminates it outputs the discrete logarithm of b with respect to a. Moreover, if c_{1}, …, c_{u} forms a generating system and u is polynomially bounded in log(q), the expected running time of the algorithm is in Õ(q^{2− \frac{2}{g}}).

The algorithm has storage requirements of Õ(q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ). More precisely, the algorithm uses only the first Õ(q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ) registers, and each register always contains elements whose bit-length is polynomially bounded in log(q).

The algorithm is given in the next subsection and the analysis in subsection 3.3.

Then we show the that there is an efficient algorithm which outputs a small system of divisor classes of degree 0 which generates the degree 0 class group with high probability (see subsection 3.5):

Proposition 3.2 Let us fix some g ≥ 1. Then there exists a randomized algorithm such that the following holds: Upon input of a curve C/𝔽_{q} of genus g and a divisor D_{0} of degree 1 as above, the algorithm computes a system of random elements c_{1}, …, c_{u} of Cl^{0}(C), represented by along D_{0} reduced divisors, where u := eℓ with e := ⌈log_{2}(# Cl^{0}(C))⌉ and ℓ := ⌈log_{2}(e) + 1⌉. Moreover, expected running time is polynomially bounded in d and log(q), and with a probability ≥ \frac{1}{2}, the system c_{1}, …, c_{u} is a generating system of Cl^{0}(C).

A problem is however that we do not know how one can in a sufficiently efficient way certify that the output is indeed a generating system. As a work-around, we proceed as follows: We assume that we have a generating system and apply the index calculus algorithm. We stop the computation if it has not terminated within a predefined time.

An obvious consequence of Proposition 3.1 is:

Proposition 3.3 Let us fix some g ≥ 2. Then there exists a randomized algorithm such that the following holds: Upon input of a curve C/𝔽_{q} of genus g, elements a, b ∈ Cl^{0}(C) with b ∈ ⟨a⟩ and a system c_{1}, …, c_{u} of elements in Cl^{0}(C) with u polynomially bounded in log(q), the algorithm either outputs “failure” or the discrete logarithm of b with respect to a. The running time of the algorithm is in Õ(q^{2− \frac{2}{g}}), and if c_{1}, …, c_{u} is a generating system, the probability of failure is ≤ \frac{1}{2}. The algorithm has storage requirements of

Õ(q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ).

Indeed, let us fix a RAM Π satisfying the claim in Proposition 3.1, and let δ ∈ ℕ such that the RAM terminates in an expected time of q^{2− \frac{2}{g}} ·log(q)^{δ} if applied to an instance as in Proposition 3.1. We apply this RAM with the input of Proposition 3.3 and terminate the execution if ⌈2 · q^{2− \frac{2}{g}} · log(q)^{δ}⌉ commands are executed (or with other words, if the uniform running time is ⌈2·q^{2− \frac{2}{g}} ·log(q)^{δ}⌉) – provided Π has not terminated at this point in time. (For this, we insert a “control unit”.) Note that then the running time of Π (as always measured with the logarithmic cost measure) is ≥ ⌈2 · q^{2− \frac{2}{g}} · log(q)^{δ}⌉. By Markov’s bound we have: If c_{1}, …, c_{u} is a generating system, with a probability of ≥ \frac{1}{2}, the algorithm outputs the discrete logarithm of b with respect to a.

By assumption, each operation performed by Π has a running time which is polynomially bounded in log(q). Therefore, the total running time is in Õ(q^{2− \frac{2}{g}}). □

The proof of Theorem 1 is now easy:

Let g ≥ 2 be fixed. Now given an instance (C, a, b) with g(C) = g as described above, we proceed as follows: First we apply an algorithm for which Proposition 3.2 holds; let the result be c_{1}, …, c_{u}. Then we apply an algorithm for which Proposition 3.3 holds to C, a, b and the system c_{1}, …, c_{u}. The expected running time is then in Õ(q^{2− \frac{2}{g}}), and moreover, the probability of failure is ≤ \frac{3}{4}. This implies Theorem 1. □

3.2 The index calculus algorithm

Again, let g ≥ 2 be fixed. We now describe an index calculus algorithm which leads to Proposition 3.1. As already stated, the algorithm uses double large prime variation. We do so by computing a tree of large prime relations. The main challenge resides in controlling the growth of the tree of large prime relations as well as its depth, that is, the maximal distance of any vertex to the root. This task is more difficult than for hyperelliptic curves in imaginary quadratic representation, where one has a concrete description of the effective divisors which are reduced along the point at infinity, and one knows that the growth process is very regular.

We now give an overview over the algorithm. Subroutines for the various steps are discussed on pages 15 – 18 in greater detail.

Broadly speaking, we proceed as follows: First we compute the group order and its factorization. We fix an 𝔽_{q}-rational point P_{0} and a factor base F. We construct a tree of large prime relations, using a “stage-wise” approach. After a tree of a suitable size has been constructed, we use the tree to generate relations over the factor base. The main idea is here that we can – via the tree – substitute large primes occurring in relations by sums of factor base elements. Finally we solve the discrete logarithm problem via sparse linear algebra.

More precisely, the factor base is a set F ⊆ C(𝔽_{q}) − \{P_{0}\} of size ⌈q^{1− \frac{1}{g}} ⌉, and the set of so-called “large primes” is L := C(𝔽_{q}) − (F ∪ {P_{0}}). Now the tree of large prime relations is a tree T whose set of vertices is contained in L ˙∪ {∗}. In the following, we denote the set of vertices of T also by T. How the tree is computed is discussed below (see again pages 15 and following).

Apart from the computation of the tree of large prime relations, the algorithm is closely related to the algorithm in [EG02]. A relatively minor difference is that in [EG02] it is assumed that the group is cyclic or a basis of it is known whereas we use only a generating system.

The input data for the algorithm are represented as described at the end of the previous section.

The algorithm for curves of a fixed genus g

Input: A curve C/𝔽_{q} of genus g, elements a, b ∈ Cl^{0}(C) with b ∈ ⟨a⟩, c_{1}, …, c_{u} ∈ Cl^{0}(C), given by an along D_{0} reduced divisors.

Output: The discrete logarithm of b with respect to a.

1. Compute N ⟵ # Cl^{0}(C) and factorize N. (Let N = ∏_{i=1}^{v} ℓ_{i}^{e_{i}} with e_{i} ∈ ℕ and pairwise distinct prime elements ℓ_{i}.)

2. Enumerate C(𝔽_{q}). Choose an 𝔽_{q}-rational point P_{0} and a factor base F = \{F_{1}, F_{2}, …, F_{k}\} ⊆ C(𝔽_{q}) − \{P_{0}\} of size ⌈q^{1− \frac{1}{g}} ⌉. (If this is not possible,

terminate.) Represent a, b, c_{1}, …, c_{u} by along P_{0} reduced divisors.

3. Construct a labeled rooted tree T with root ∗ whose set of vertices is contained in L ˙∪ {∗}, as described below.

4. 4.1. Let t ⟵ ⌈log_{2}(k + u) + log_{2}(2 log_{2}(N))⌉ + 1

4.2. Construct matrices R ∈ (ℤ/Nℤ)^{(2(k+u)·t)×k} and S ∈ (ℤ/Nℤ)^{(2(k+u)·t)×u} in sparse representation as well as vectors \underline{α}, \underline{β} ∈ (ℤ/Nℤ)^{2(k+u)·t} as follows: 4.2.1. For i = 1, …, (k + 2u) · t do

Choose uniformly and independently randomly α, β, s_{1}, …, s_{u} ∈ ℤ/Nℤ and compute the unique along P_{0} reduced divisor D with [D] − deg(D) · [P_{0}] = ∑_{j} s_{j}c_{j} + αa + βb in free representation.

Until D splits into elements of F ∪ T. Use the tree T to substitute these elements by sums of multiples of elements of F. Let

∑_{j} r_{i,j}[F_{j}] − r_{i}[P_{0}] = ∑_{j} s_{i,j}c_{j} + α_{i}a + β_{i}b

with r_{i} = ∑_{j} r_{i,j} be the relation generated. 4.2.2. For i_{1} = 1, …, k

For i_{2} = 1, …, t Let i ⟵ (i_{1} − 1) · t + i_{2} + (k + 2u) · t. Choose uniformly and independently randomly α, β, s_{1}, …, s_{u} ∈ ℤ/Nℤ and compute the unique along P_{0} reduced divisor D with [D]−deg(D)·[P_{0}] = [F_{i_{1}}] − [P_{0}] + ∑_{j} s_{j}c_{j} + αa + βb.

Until D splits into elements of F ∪ T. Use the tree T to substitute these elements by sums of multiples of elements of F. Let

∑_{j} r_{i,j}[F_{j}] − r_{i}[P_{0}] = ∑_{j} s_{j}c_{j} + α_{i}a + β_{i}b

with r_{i} = ∑_{j} r_{i,j} be the relation generated.

5. Try to compute a row vector \underline{γ} ∈ (ℤ/Nℤ)^{1×(2(k+u)·t)} with \underline{γ}(R|S) = 0 and [\underline{γ}]_{ℓ} ≠ 0 for all prime divisors ℓ of N with an algorithm for sparse linear algebra as discussed below.^{2} If this fails, go back to Step 4.

6. If ∑_{i} γ_{i}β_{i} ∈ (ℤ/Nℤ)^{∗}, let ξ := −\frac{∑_{i} γ_{i}α_{i}}{∑_{i} γ_{i}β_{i}}, otherwise go back to Step 4.

2For an integer a and a natural number n we denote the residue class of a in ℤ/nℤ by [a]_{n}.

7. Compute ord(a), using the factorization of N. Output the unique non-negative number x ∈ {0, …, ord(a) − 1} with [x]_{ord(a)} = [ξ]_{ord(a)}.

It is immediate that the algorithm is correct, that is, if it terminates it outputs the discrete logarithm of b with respect to a.

As already mentioned, details on the various steps of the algorithm will be given below. However, merely under an assumption on the linear algebra algorithm, we can already now give an upper bound on the number of expected iterations of Steps 4 – 6, conditionally to any outcome of Step 3:

Proposition 3.4 Let the linear algebra algorithm be such that the following holds: If applied to a matrix M in sparse representation over ℤ/Nℤ, then

• the algorithm terminates in a finite expected time, and it either outputs a vector \underline{γ} over ℤ/Nℤ with \underline{γ}M = 0 and [\underline{γ}]_{ℓ} ≠ \underline{0} for all prime divisors ℓ of N or it outputs “failure”,

• if moreover the matrix M has full column rank, the algorithm succeeds (that is, outputs a vector as desired) with a probability of Ω(1).

If then c_{1}, …, c_{u} forms a generating system, conditionally to any outcome of Step 3, the probability that the algorithm fails in Step 5 or Step 6 (that is, it returns to Step 4) is in O(log log(q)).

This proposition is essentially proven in [EG02]. We recall two major ingredients of the proof.

First, one can show that the probability that the matrix (R|S) has full column rank is in Ω(1). This follows from Lemma 4.1 in [Pom87] and the subsequent remarks. We note that the proof in [Pom87] is very sketchy; a more complete argument is given in [Heß05] (see part (i) of [Heß05, Lemma 64]).

Moreover, the random vector \underline{β} is independent of (R|S). This implies that the probability that ∑_{i} γ_{i}β_{i} is invertible is \frac{φ(N)}{N}, which is in Ω(\frac{1}{log log(N)}) = Ω(\frac{1}{log log(q)}) (see [RS62]). □

Subroutines

We now give some more information on various steps of the algorithm.

Step 1 – Computation of the group order and factorization

The L-polynomial of a curve over 𝔽_{q} given by a plane model of bounded degree can be computed (with a deterministic algorithm) in a time which is polynomially bounded in log(q). (This follows from [Pil91, Theorem H] which in turn relies on Pila’s extension of the point counting algorithm by Schoof ([Sch85]) to abelian varieties ([Pil90]).) This means in particular that the order of the degree 0 class group can be computed in polynomial time in log(q).

It is well known that an integer N can be factored in subexponential time in log(N); see for example [Pom87].

Step 2 – Construction of the factor base

As assumed in the previous section, let x : C ⟶ ℙ_{k}^{1} be separable. Then one can iterate over all points of C(𝔽_{q}) in an expected time of Õ(q) as follows: One iterates over all points P ∈ ℙ^{1}(𝔽_{q}) and factorizes the ideal x^{−1}(P) (that is, one computes a free representation). For each point P, this step requires an expected time which is polynomially bounded in log(q). In total Step 2 can be performed in an expected time of Õ(q).

Step 3 – Generation of the tree of large prime relations

The tree of large prime relations is a labeled rooted tree whose vertex set is contained in L ˙∪ {∗} with root ∗. It is constructed as follows:

We repeatedly choose uniformly randomly s_{1}, …, s_{u} ∈ ℤ/Nℤ and compute the along P_{0} reduced effective divisor D in free representation with

[D] − deg(D) · [P_{0}] = ∑_{j=1}^{u} s_{j} c_{j} ,  (3)

where P_{0} ∈ C(𝔽_{q}) is the point computed above.^{3} Note that as mentioned in the previous section, the computation of D is possible in an expected time which is polynomially bounded in log(q).

Following [GTTD07] and other works, we define:

Definition 3.5 A relation involving only input elements and factor base elements, that is, a relation of the form ∑_{j} r_{j}[F_{j}] = ∑_{j} s_{j}c_{j} + αa + βb is called a Full relation. A relation which additionally involves one large prime, that is, a relation of the form ∑_{j} r_{j}[F_{j}] + r_{P} [P] = ∑_{j} s_{j}c_{j} + αa + βb with P ∈ L and r_{P} ≠ 0 is called an FP relation. A relation which involves two large primes, that is, a relation of the form ∑_{j} r_{j}[F_{j}] + r_{P} [P] + r_{Q}[Q] = ∑_{j} s_{j}c_{j} + αa + βb with P, Q ∈ L, P ≠ Q and r_{P} , r_{Q} ≠ 0 is called a PP relation. Here r_{j}, r_{P} , r_{Q} ∈ ℤ/Nℤ.

As usual, during the construction of the tree, FP relations are stored as labeled edges connecting the large prime with the root ∗, and PP relations are stored as labeled edges connecting the two large primes.

3Note here that if we represent divisor classes by along P_{0} reduced divisors in free representation, to compute the divisor D is the same as computing the sum ∑_{j=1}^{u} s_{j} c_{j} in the degree 0 class group.

As already mentioned, we construct the tree in stages. During each stage we only attach edges to the tree which are connected to vertices constructed in the previous stages. In Stage 1, we attach ⌈q^{1−1/g}⌉ edges coming from FP relations to the root ∗. Thereafter, we terminate Stage s and start Stage s + 1 whenever the tree has 2^{s−1} · ⌈q^{1−1/g}⌉ edges.

The construction of the tree is abandoned if a predefined number of edges N_{max} is reached. We could for example set N_{max} := ⌈q/4⌉. We will however argue in the analysis of the algorithm in the next subsection that N_{max} := ⌈q^{1−1/g+1/g^{2}}⌉ suffices. This smaller value of N_{max} only lowers the time for the construction of the tree by a constant factor but decreases the storage requirements substantially. This is analogous to the situation in [GTTD07].

Altogether, we have the following procedure for construction of a suitable tree of large prime relations. In the procedure we construct a labeled tree called T. The edges of the tree are labeled with the corresponding relations; the vertices are labeled too, namely with the stage at which they inserted into the tree. We denote the subtree of T which has been constructed until (including) stage s by T_{s}. In other words: A vertex of T occurs in T_{s} if and only if its label is ≤ s.

Procedure: Construction of the tree of large prime relations

Construct a labeled rooted tree T with vertex set contained in L ˙∪ {∗} as follows: Let T consist only of the root ∗, labeled with 0. Let N_{max} ⟵ ⌈q^{1−1/g+1/g^{2}}⌉. Let s ⟵ 1. Repeat

Repeat Choose s_{1}, …, s_{u} ∈ ℤ/Nℤ uniformly and independently at random. Compute the along P_{0} reduced divisor D in free representation with [D] − deg(D) · [P_{0}] = ∑_{j} s_{j}c_{j}. If D splits as D = ∑_{j} r_{j}F_{j} + Q with Q ∈ L − (F ∪ T),

insert an edge from ∗ to Q into T, labeled with (r_{j})_{j} (in sparse representation).

If D splits as D = ∑_{j} r_{j}F_{j} +r_{P} P +Q with P ∈ T_{s−1}, Q ∈ L−(F ∪T)

and r_{P} > 0,

insert an edge from P to Q into T, labeled with (r_{j})_{j} and r_{P}. In both cases label Q with s and the edge with (r_{j})_{j} (in sparse representation).

Until T contains min{2^{s−1} · ⌈q^{1−1/g}⌉, N_{max}} edges.

If the number of edges equals N_{max}, STOP.

Let s ⟵ s + 1.

This construction of the tree guarantees that the depth of the tree is always in O(log(q)) (see also inequality (7) in the next subsection). The main difficulty of the analysis of the procedure resides in proving that a tree of sufficient size can be constructed in an expected time of Õ(q^{2−2/g}). This is verified in the next subsection.

Step 5 – Linear algebra

For the linear algebra computation we use an algorithm which satisfies the following condition (and thus also Proposition 3.4).

If applied to a matrix M ∈ (ℤ/Nℤ)^{m×n} with m ≥ n and weight ω in sparse representation,

• the algorithm always terminates in an expected time of Õ(n · (m + ω) · log(mN)^{O(1)}), and it either outputs a vector \underline{γ} over ℤ/Nℤ with \underline{γ}M = 0 and [\underline{γ}]_{ℓ} ≠ \underline{0} for all prime divisors ℓ of N or it outputs “failure”,

• if moreover the matrix M has full column rank, the algorithm succeeds with a probability of Ω(1).

Here the weight of a matrix is the number of non-zero entries.

Such an algorithm is given in [EG02, Section 4].

Step 7 – Computation of the order of a

The computation of ord(a) can be performed efficiently (in polynomial time in log(N) ∈ O(log(q))) along the following lines:

As in the algorithm, let N = ∏_{i=1}^{v} ℓ_{i}^{e_{i}} with e_{i} ∈ ℕ and pairwise distinct prime numbers ℓ_{i}. Now let L_{i} := _{\frac{N}{ℓ_{i}^{e_{i}}}}, and let o_{i} := min\{j ∈ 0, …, e_{i} | ℓ_{i}^{j}L_{i} · a = 0} for i = 1, …, v. Then ∏_{i=1}^{v} ℓ_{i}^{o_{i}} is the order of a.

3.3 Analysis of the index calculus algorithm

We now show that with the algorithm outlined in the previous subsection, one can compute a solution to the discrete logarithm problem for curves of the fixed genus g in an expected time of Õ(q^{2−2/g}) – provided that the system c_{1}, …, c_{u} is a generating system and u is polynomially bounded in log(q).

Steps 1 and 2 – computation of the group order, factorization, construction of the factor base

We have already argued that one can perform these steps in an expected time of Õ(q).

Step 3 – construction of the tree of large prime relations

The analysis of the growth of the tree relies crucially on the following proposition.

Proposition 3.6 For curves of fixed genus g over finite fields 𝔽_{q}, the number of special effective divisors of degree g is in O(q^{g−1}).

Recall that an effective divisor D is called special if the linear system |K −D| is non-empty, where K is a canonical divisor. Note that by the Riemann-Roch theorem, an effective divisor of degree g is non-special if and only if the linear system |D| merely contains D itself.

Note that map D ↦ [D] gives an injection from the set of non-special divisors of degree g into the set of divisor classes of degree g, and therefore, the map D ↦ [D − g · P_{0}] gives an injection from the set of non-special divisors of degree g into the degree 0 divisor class group. Then we can apply the bijection between the degree 0 class group and the set of along P_{0} reduced divisors.

Explicitly, let D be a non-special effective divisor of degree g, and let D′ be the unique effective divisor of minimal degree with D′ + (deg(D) − deg(D′)) · P_{0} = D. Then D′ is reduced along P_{0}, and it is the along P_{0} reduced divisor which represents the class [D − g · D_{0}].

We assume that Proposition 3.6 is well known to many experts in curves and function fields. For the lack of a suitable reference we give a proof in the next subsection. Note that a straightforward application of the Hasse-Weil bound merely gives that the number in question is in O(q^{g−1/2}).

This proposition makes it possible to discard all special divisors in the analysis of the construction of the tree of large prime relations.

Let C > 0 be such that for all curves of genus g over any finite fields 𝔽_{q} the number of special divisors of degree g is ≤ C · q^{g−1}.

As in the previous subsection, let N_{max} := ⌈q^{1−1/g+1/g^{2}}⌉ be the number of edges (that is, the number of vertices different from ∗) at which the construction of the tree is stopped.

The conditions

N_{max} + #F ≤ q/4  #(C(𝔽_{q}) − \{P_{0}\}) ∈ [max\{q^{1− \frac{1}{g}} , q/2\}, 2q]
# Cl^{0}(C) ≤ 2q^{g}  q ≥ (4 · g! · C)^{g}

hold for q large enough; we assume that they are satisfied.

Note that by our assumption that c_{1}, …, c_{u} generate Cl^{0}(C), if s_{1}, …, s_{u} are uniformly distributed random elements from ℤ/Nℤ, ∑_{i} s_{i}c_{i} is uniformly distributed in Cl^{0}(C). This means that the divisor D in (3) is uniformly distributed in the set of all effective divisors which are reduced along P_{0}.

By our assumptions on q, we always have

#(C(𝔽_{q}) − (T ∪ F ∪ {P_{0}}) ≥ q/2 − q/4 = q/4 .  (4)

Let Div^{g}(C) be the set of effective divisors of degree g on C, and let Div^{g,ns}(C) (resp. Div^{g,s}(C)) be the subset of non-special (resp. special) effective divisors of degree g.

Let us first assume that we are still in Stage 1, that is, only relations with one large prime (not yet in the tree) are considered.

Let us thus assume we are given the tree T with < ⌈q^{1−1/g}⌉ edges. We want to bound the expected number of relations (3) needed until a new edge is inserted into the tree.

Let

\begin{matrix}D := \{P_{1} + ⋯ + P_{g} ∈ Div^{g}(C) | ∀i = 1, …, g − 1 : P_{i} ∈ F, \\ P_{g} ∈ C(𝔽_{q}) − (T ∪ F ∪ \{P_{0}\})\} , \end{matrix}

D^{ns} := D ∩ Div^{g,ns}(C) .

Note that any divisor D ∈ D^{ns} is reduced along P_{0} (because P_{0} is not contained in the support of D and the linear system |D| consists merely of D). If a divisor D = P_{1} +⋯+P_{g} as in the set D^{ns} appears in a relation (3), a new edge is inserted into the tree. (Other divisors might also lead to new edges: We ignore special divisors, and we ignore divisors of degree < g.)

We have

\begin{matrix}#D = \binom{#F+g−2}{g−1} · #(C(𝔽_{q}) − (T ∪ F ∪ \{P_{0}\})) ≥ \frac{#F^{g−1}}{(g−1)!} · q/4 by (4) \\ ≥ \frac{1}{4(g−1)!} · q^{\frac{(g−1)^{2}}{g}} · q = \frac{1}{4(g−1)!} · q^{\frac{g^{2}−g+1}{g}} = \frac{1}{4(g−1)!} · q^{g−1+ \frac{1}{g}} . \end{matrix}

(5)

By our assumption that q ≥ (4 · g! · C)^{g}, we have

# Div^{g,s}(C) ≤ Cq^{g−1} ≤ \frac{1}{4g!} · q^{g−1+ \frac{1}{g}} ≤ \frac{1}{8(g − 1)!} · q^{g−1+ \frac{1}{g}} .  (6)

Inequalities (5) and (6) imply

#D^{ns} ≥ \frac{1}{8(g − 1)!} · q^{g−1+ \frac{1}{g}} .

Together with our assumption that # Cl^{0}(C) ≤ 2q^{g}, this implies that the probability that a relation (3) enlarges the tree is

≥ \frac{#D^{ns}}{# Cl^{0}(C)} ≥ \frac{1}{16(g − 1)!} · q^{−(1− \frac{1}{g})} .

The expected number of relations (3) which have to be considered until the tree is enlarged is thus

≤ 16(g − 1)! · q^{1− \frac{1}{g}} .

This implies that the expected number of tries until the tree has ⌈q^{1− \frac{1}{g}} ⌉ edges is

≤ 16(g − 1)! · q^{1− \frac{1}{g}} · ⌈q^{1− \frac{1}{g}} ⌉ ≤ 16(g − 1)! · (q + 1)^{2− \frac{2}{g}} .

We now assume that s ≥ 2 and a tree T with < 2^{s−1} · ⌈q^{1−1/g}⌉ edges containing a subtree T_{s−1} with 2^{s−2} · ⌈q^{1−1/g}⌉ edges, has already been constructed. The task is again to derive a bound on the expected number of relations (3) needed until the tree is enlarged.

Similarly to the above, let

\begin{matrix}D := \{P_{1} + ⋯ + P_{g} ∈ Div^{g}(C)| ∀i = 1, …, g − 2 : P_{i} ∈ F, \\ P_{g−1} ∈ F ∪ T_{s−1}, P_{g} ∈ C(𝔽_{q}) − (T ∪ F ∪ \{P_{0}\})\} , \end{matrix}

D^{ns} := D ∩ Div^{g,ns}(C) .

We now have

#D = (\binom{#F+g−2}{g−1} + \binom{#F+g−3}{g−2} · #(T_{s−1} − \{∗\})) · #(C(𝔽_{q}) − (T ∪ F ∪ \{P_{0}\}))

≥ (\frac{#F^{g−1}}{(g−1)!} + \frac{#F^{g−2}}{(g−2)!} · 2^{s−2} · q^{1−1/g}) · q/4
≥ (\frac{1}{(g−1)!} · q^{\frac{(g−1)^{2}}{g}} + \frac{1}{(g−2)!} · 2^{s−2} · q^{\frac{(g−1)^{2}}{g}}) · q/4
= (\frac{1}{4(g−1)!} + \frac{1}{4(g−2)!} · 2^{s−2}) · q^{g−1+ \frac{1}{g}} .

Together with (6), this implies

#D^{ns} ≥ \frac{1}{4(g − 2)!} · 2^{s−2} · q^{g−1+ \frac{1}{g}} .

This implies that the probability that a relation (3) enlarges the tree is

≥ \frac{1}{8(g − 2)!} · 2^{s−2} · q^{−(1− \frac{1}{g})} .

The expected number of relations (3) which have to be considered until the tree is enlarged is thus

≤ 8(g − 2)! · \frac{1}{2^{s−2}} · q^{1− \frac{1}{g}} .

This implies that given any tree T_{s−1} with 2^{s−2} · ⌈q^{1− \frac{1}{g}} ⌉ edges, the expected number of tries until a tree T with min\{2^{s−1} · ⌈q^{1− \frac{1}{g}} ⌉, N_{max}\} edges is constructed is

≤ 16(g − 2)! · (q + 1)^{2− \frac{2}{g}} .

We have s ∈ O(log(q)) as can be easily seen: During the execution of the procedure we always have for s ≥ 2

2q ≥ #(T − \{∗\}) ≥ #(T_{s−1} − \{∗\}) = 2^{s−2} · ⌈q^{1− \frac{1}{g}} ⌉ ,

i.e.

s ≤ log_{2}(q^{\frac{1}{g}}) + 3 = \frac{1}{log(2) · g} · log(q) + 3 ∈ O(log(q)) .  (7)

It follows that in total an expected number of O(log(q) · q^{2− \frac{2}{g}}) relations (3) have to be considered until the tree has N_{max} edges. As each of these relations can be obtained in an expected time which is polynomially bounded in log(q), we conclude that a tree with N_{max} edges can be constructed in an expected time of

Õ(q^{2− \frac{2}{g}}) .

Note that the depth of the tree is always bounded by s. In particular, as s ∈ O(log(q)), the depth of the tree is also in O(log(q)).

Step 4 – relation generation

We now assume we have constructed a tree T with N_{max} = ⌈q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ⌉ edges. Similarly to the above let

D := {P_{1} + ⋯ + P_{g} ∈ Div^{g}(C)| ∀i = 1, …, g : P_{i} ∈ F ∪ (T − {∗})} ,

D^{ns} := D ∩ D^{g,ns} .

Then D contains ≥ \frac{1}{g!} · (#F + #(T − \{∗\}))^{g} ≥ \frac{1}{g!} · q^{g−1+ \frac{1}{g}} elements. By

the first two inequalities of (6), D^{ns} contains at least \frac{3}{4g!} · q^{g−1+ \frac{1}{g}} elements. This means that the probability that the divisor D in relation (3) splits into elements of the factor base or vertices of the tree is

≥ \frac{3}{8g!} · q^{−(1− \frac{1}{g})} .

The expected number of relations

[D] − deg(D) · [P_{0}] = αa + βb  (8)

which have to be considered in each iteration of the For-loops is in O(q^{1− \frac{1}{g}}). As each relation (8) can be obtained in an expected time which is polynomially bounded in log(q^{g}), this means that the expected running time of one iteration in the For-loops is in Õ(q^{1− \frac{1}{g}}).

We have to generate 2(k + u) · t ∈ Õ(#F) = Õ(q^{1− \frac{1}{g}}) “combined” Full relations. This means that the total running time of this step of the algorithm is in Õ(q^{2− \frac{2}{g}}).

Step 5 – linear algebra

The linear algebra takes place on a sparse matrix with Õ(q^{1−1/g}) rows and O(q^{1−1/g}) columns.

As the tree has depth O(log(q)) and the size of the generating system is by assumption polynomially bounded in log(q), every row of the matrix (R|S) contains only log(q)^{O(1)} non-zero entries. As pointed out in the previous subsection, the computation can then be performed in an expected time of Õ(q^{2−2/g}).

Final result

We have seen that Steps 1 – 5 of the algorithm all have an expected running time of Õ(q^{2− \frac{2}{g}}). Moreover, by Proposition 3.4 and the properties of the linear algebra algorithm, after an expected number of O(log log(N)) ⊆ O(log(q)) restarts of the computation of the matrix (R|S), the linear algebra computation leads the solution to the discrete logarithm problem. This means that the total running time is in

Õ(q^{2− \frac{2}{g}}) ,

in accordance with the statement in Proposition 3.1.

Storage requirements

Clearly one can obtain: Only the first Õ(q^{1− \frac{1}{g} + \frac{1}{g^{2}}} ) registers are used and the bit-length of each number stored is polynomially bounded in log(q).

3.4 On the number of special divisors

The purpose of this subsection is to prove Proposition 3.6.

We consider curves of a fixed genus g over finite fields.

Let C be such a curve over 𝔽_{q}. Let Div^{g}(C) be the set of effective divisors of degree g on C, and let E be a divisor of degree g on C. We have the surjective map Div^{g}(C) ⟶ Cl^{0}(C), D ↦ [D] − [E]. Note that the set of special divisors of degree g is exactly the subset of Div^{g}(C) where the map to Cl^{0}(C) is not injective.

The number of special divisors is therefore bounded from above by 2 (# Div^{g}(C)−# Cl^{0}(C)), and it suffices to prove that # Div^{g}(C)−# Cl^{0}(C) ∈ O(q^{g−1}).

We follow the exposition to the zeta-function in [Sti93]. Note however that we use different symbols for the indices.

Let L = ∏_{i=1}^{2g}(1 − α_{i}t) ∈ ℂ(t) be the L-polynomial of C, let A_{n} be the number of effective divisors of degree n, let B_{n} be the number of prime divisors of degree n on C, and let^{4}

S_{n} := ∑_{i=1}^{2g} α_{i}^{n} .

As the α_{i} can be arranged such that α_{i}α_{g+i} = q for all i = 1, …, g, we have

# Cl^{0}(C) = L(1) ∈ q^{g} − S_{1} · q^{g−1} + O(q^{g−1}) .

with S_{1} ∈ O(\sqrt{q}). We thus have to show that

A_{g} ∈ q^{g} − S_{1} · q^{g−1} + O(q^{g−1}) .

We will in fact show the more general statement

A_{n} ∈ q^{n} − S_{1} · q^{n−1} + O(q^{n−1})  (9)

for any fixed n ∈ ℕ.

Let us fix the following definition.

Definition 3.7 Let D be an effective divisor of degree n on C such that D = ∑_{ℓ=1}^{n} D_{ℓ}, where D_{ℓ} is a sum of e_{ℓ} prime divisors of degree ℓ. Then the vector \underline{e} = (e_{ℓ})_{ℓ} ∈ ℕ_{0}^{n} (with ∑_{ℓ} ℓe_{ℓ} = n) is called the decomposition type of D.

By sorting effective divisors of degree n by decomposition types, we obtain

A_{n} = ∑_{\underline{e}} ∏_{ℓ} \binom{B_{ℓ} + e_{ℓ} − 1}{e_{ℓ}} ,  (10)

where the sum runs over all \underline{e} ∈ ℕ_{0}^{n} with ∑_{ℓ} e_{ℓ}ℓ = n and the products run over ℓ ∈ {1, …, n}. We have

A_{1} = B_{1} = q + 1 − S_{1} ,

which establishes the claim for n = 1. So let n ≥ 2. By [Sti93, Proposition V.2.9], we have

\begin{aligned}B_{ℓ} = \frac{1}{ℓ} · ∑_{m|ℓ} μ(\frac{ℓ}{m})(q^{m} − S_{m}) & ∈ \frac{1}{ℓ} · q^{ℓ} + O(q^{ℓ/2}) \\ & ⊆ \frac{1}{ℓ} · q^{ℓ} + O(q^{ℓ−1}) \end{aligned}  (11)

for ℓ ≥ 2.

4The definition of S_{n} follows Equation (2.25) in [Sti93]. In [Sti93, Corollary V.1.17] an analogous definition is made with opposite sign.

This implies that

\begin{aligned}A_{n} & ∈ ∑_{\underline{e}} \frac{1}{e_{1}!}(q − S_{1})^{e_{1}} · ∏_{ℓ≥2} \frac{1}{e_{ℓ}!} · \frac{1}{ℓ^{e_{ℓ}}} · q^{ℓ·e_{ℓ}} + O(q^{n−1}) \\ & ⊆ ∑_{\underline{e}}(∏_{ℓ} \frac{1}{e_{ℓ}!} · \frac{1}{ℓ^{e_{ℓ}}}) · (q^{n} − e_{1} · S_{1} · q^{n−1}) + O(q^{n−1}) . \end{aligned}

In order to derive (9) it remains to be shown that

∑_{\underline{e}} ∏_{ℓ} \frac{1}{e_{ℓ}!} · \frac{1}{ℓ^{e_{ℓ}}} = 1  (12)

and

∑_{\underline{e}} e_{1} · ∏_{ℓ} \frac{1}{e_{ℓ}!} · \frac{1}{ℓ^{e_{ℓ}}} = 1 .  (13)

Equation (12) is equivalent to

∑_{\underline{e}} n! · ∏_{ℓ} \frac{1}{e_{ℓ}!} · \frac{1}{ℓ^{e_{ℓ}}} = n! .  (14)

This is true because for any \underline{e} ∈ ℕ_{0}^{n} with ∑_{ℓ} e_{ℓ}ℓ = n, the set of permutations on n elements having exactly e_{ℓ} ℓ-cycles (for ℓ = 1, …, n) has n! · ∏_{ℓ} \frac{1}{e_{ℓ}!} · \frac{1}{ℓ^{e_{ℓ}}} elements.

We come to Equation (13). Note that we have a bijection

\begin{matrix}\{\underline{e} ∈ ℕ_{0}^{n}| ∑_{ℓ} e_{ℓ}ℓ = n, e_{1} ≠ 0\} & ⟶ & \{\underline{e}′ ∈ ℕ_{0}^{n−1}| ∑_{ℓ} e′_{ℓ}ℓ = n − 1\} , \\ \underline{e} & ↦ & \underline{e}′ \end{matrix}

with e′_{1} = e_{1} − 1 and e′_{i} = e_{i} for all i = 1, …, n − 1.

Equation (13) is then equivalent to

∑_{\underline{e}′} ∏_{ℓ} \frac{1}{e′_{ℓ}!} · \frac{1}{ℓ^{e′_{ℓ}}} = 1 ,  (15)

where the sum runs over all \underline{e}′ ∈ ℕ_{0}^{n−1} with ∑_{ℓ} e′_{ℓ}ℓ = n−1 and the products run over ℓ ∈ {1, …, n − 1}. We already know that this equation holds.

3.5 Finding a generating system

The main purpose of this subsection is to show Proposition 3.2. Note that in Proposition 3.2 we only consider curves of a fixed genus, represented by plane models of bounded degree. In this subsection, we consider arbitrary curves over finite fields. We show below how one can efficiently compute a small system of degree 0 divisor classes which with a probability ≥ \frac{1}{2} generates the degree 0 class group, provided the L-polynomial is known (see Proposition 3.17). Proposition 3.2 follows from this statement and the fact – already mentioned in subsection 3.2 –, that one can then compute the L-polynomial in a time which is polynomially bounded in log(q) ([Pil90], [Pil91]). On our way to prove Proposition 3.17, we also show how one can efficiently compute a uniformly randomly distributed effective divisor of a specific degree, provided one knows the L-polynomial, a result which might be of independent interest (see Proposition 3.16).

As usual, curves are represented by plane models, and divisors are given in ideal representation, as detailed in Section 2.

Proposition 3.8 Given a curve C over a finite field 𝔽_{q}, represented by a plane model of degree d, and a natural number n, one can with a randomized algorithm

• decide if C has an 𝔽_{q}-rational point

• if this is the case, compute such a point which is uniformly randomly distributed in C(𝔽_{q})

in an expected time which is polynomially bounded in d · log(q).

Proof. We still assume that the covering x : C ⟶ ℙ_{𝔽_{q}}^{1} is separable, and as usual we set r := deg(x).

By the Hasse-Weil bound, we have #C(𝔽_{q}) ≥ q + 1 − 2gq^{1/2}. This means that for q ≥ 4g^{2}, C(𝔽_{q}) is non-empty. The algorithm depends on a case distinction:

If q < d^{4} we compute a list of the elements in C(𝔽_{q}) by iterating over all elements P of ℙ^{1}(𝔽_{q}) and computing for each such P the divisor x^{−1}(P) in free representation. If it turns out that C(𝔽_{q}) is empty, we output that this is the case, otherwise we choose one of the points in C(𝔽_{q}) uniformly at random. We have already argued in subsection 3.3 that this computation can be performed in an expected time which is polynomially bounded in d · q, that is, in an expected time which is polynomially bounded in d as q is also polynomially bounded in d by assumption.

If q ≥ d^{4} (such that q > 4g^{2} and therefore C(𝔽) ≠ ∅), we proceed with the following algorithm.

Algorithm for computation of a uniformly randomly distributed rational point on a curve over a finite field

Input: A curve C/𝔽_{q}, represented by a plane model, with C(𝔽_{q}) ≠ ∅.

1. Choose a point P ∈ ℙ^{1}(𝔽_{q}) uniformly at random.

2. Compute x^{−1}(P) in free representation.

3. Let P_{1}, …, P_{a} be the distinct 𝔽_{q}-rational points occurring in x^{−1}(P).

(The other prime divisors in the support of x^{−1}(P) are ignored, and a = 0 is possible.)

4. Choose a number i in {1, …, r} uniformly at random.

5. If i ≤ a, output P_{i}, otherwise go back to Step 1.

Without any assumption on q and g, this algorithm computes a uniformly randomly distributed point in C(𝔽_{q}) provided that this set is non-empty, as we show now.

The computation of Steps 1 – 5 can be performed in an expected time which is polynomially bounded in d · log(q).

Let us analyze the algorithm: After Step 4 the following always holds: The random variable (P, i) is uniformly distributed on the set ℙ^{1}(𝔽_{q}) × {1, …, r}, which has (q + 1) · r elements. This means that in every iteration of the algorithm, the probability that the algorithm terminates in Step 5 is always \frac{#C(𝔽_{q})}{(q+1)·r}, and if this is the case, every point in C(𝔽_{q}) is chosen with the same probability of \frac{1}{#C(𝔽_{q})}.

It follows that the output of the algorithm is a uniformly randomly distributed element in C(𝔽_{q}). Moreover, the expected number of iterations is \frac{(q+1)·r}{#C(𝔽_{q})}. In order to prove the proposition, we therefore have to show that the quantity \frac{q+1}{#C(𝔽_{q})} is polynomially bounded in d · log(q); we show that it is polynomially bounded in g (which in turn is polynomially bounded in d).

We have #C(𝔽_{q}) ≥ q +1−2gq^{1/2} by the Hasse-Weil bound. For q ≥ 16g^{2} we have #C(𝔽_{q}) ≥ \frac{q}{2} + 1, and therefore \frac{q+1}{#C(𝔽_{q})} ≤ 2. On the other hand, for q < 16g^{2} the quantity \frac{q+1}{#C(𝔽_{q})} is clearly polynomially bounded in g. □

Proposition 3.9 Given a curve C over a finite field 𝔽_{q}, represented by a plane model of degree d and a natural number n, one can with a randomized algorithm

• decide if C has a prime divisor of degree n

• if this is the case compute such a prime divisor which is uniformly randomly distributed in the set of all prime divisors of C of degree n

in an expected time which is polynomially bounded in d · n · log(q).

Proof. As in subsection 3.4, let B_{n} be the number of prime divisors of C of degree n. Then we have (cf. [Sti93, Corollary V.2.10.]):

B_{n} ≥ \frac{q^{n}}{n} − (2 + 7g) · \frac{q^{n/2}}{n}

For q > (2 + 7g)^{2/n} we therefore have B_{n} ≥ 1.

Similarly to the algorithm for the previous proposition, we have a case distinction according to q > (2 + 7d^{2})^{2}.

In both cases we consider 𝔽_{q^{n}}-rational points of C_{𝔽_{q^{n}}}. Note that given such a point, one can compute the associated prime divisor (=closed point) of C by computing the intersection of the corresponding prime ideal with the function field 𝔽_{q}(C) in a time which is polynomially bounded in d · n · log(q) (cf. Section 2).

If q ≤ (2 + 7d^{2})^{2}, we iterate over all 𝔽_{q^{n}}-rational points of C_{𝔽_{q^{n}}} (as described at the beginning of the proof of Proposition 3.8). For each such point we compute the associated prime divisor (=closed point) of C, and check if this is a prime divisor of degree n. Like this we check if a prime divisor of degree n on C exists, and if this is the case, we uniformly randomly choose one.

So let now q > (2 + 7d^{2})^{2}. Then in particular q > (2 + 7d^{2})^{2/n}, and therefore there is a prime divisor of degree n on C. Then the algorithm is also easy: We first choose an 𝔽_{q^{n}}-rational point of C_{𝔽_{q^{n}}} uniformly at random compute the associated prime divisor (=closed point) of C. If the prime divisor has degree n, we output it, otherwise we repeat this process.

Here we compute the 𝔽_{q^{n}}-rational point using an algorithm for Proposition 3.8, adapted to work over extension fields. The expected time of one iteration is polynomially bounded in d·n·log(q). We therefore have to show that the number of iterations is polynomially bounded in d · n · log(q).

The number of points in C(𝔽_{q^{n}}) such that the associated prime divisor of C has degree n is n · B_{n}. Therefore the probability that a uniformly distributed point in C(𝔽_{q^{n}}) does not give rise to a prime divisor of degree n is \frac{#C(𝔽_{q^{n}})−nB_{n}}{#C(𝔽_{q^{n}})} which is ≤ \frac{(2+9g)·q^{n/2}}{q^{n}−2gq^{n/2}} = \frac{(2+9g)}{q^{n/2}−2g}. For q ≥ (4 + 20g)^{2/n} this is ≤ \frac{1}{2}. If this bound in not satisfied, the probability that a uniformly distributed point in C(𝔽_{q^{n}}) does give rise to a prime divisor of degree n is in \frac{1}{g^{Ω(1)}} . □

We aim at giving an efficient algorithm to compute a random effective divisor which is uniformly randomly distributed in the set of all effective divisors of a specific degree. We give some definitions and notations first for which we fix a curve C over a finite field.

Definition 3.10 Let n ∈ ℕ_{0} and m ∈ ℕ. Then, as usual, an effective divisor on C of degree n which is the sum of prime divisors of degree at most m is called m-smooth or (n, m)-smooth. An effective divisor on C of degree n which is the sum of prime divisors of degree exactly m is called m-homogeneous or (n, m)-homogeneous.

Notation 3.11 Let n ∈ ℕ_{0} and m ∈ ℕ. Then the number of effective divisors on C of degree n which split into prime divisors of degree ≤ m (resp. = m, resp. ≥ m) is denoted by ψ_{≤}(n, m) (resp. ψ_{=}(n, m), resp. ψ_{≥}(n, m)).

Note that in the notation of subsection 3.4,

ψ_{≤}(n, n) = A_{n} and ψ_{=}(n, n) = B_{n} .

Definition 3.12 Let D be an (r · m, m)-homogeneous divisor on C. Then the multiplicity type \underline{μ} ∈ ℕ_{0}^{r} of D is defined as follows: μ_{i} is the number of prime divisors occurring with multiplicity exactly i in D.

Note that ∑_{i=1}^{r} iμ_{i} = r.

Proposition 3.13 There exists a randomized algorithm such that the following holds: Given a natural number m, a curve C over a finite field 𝔽_{q}, represented by a plane model of degree d, such that C has at least one prime divisor of degree m, the number B_{m} of prime divisors of degree m on C as well as another natural number r, the algorithm computes an effective divisor on C which is uniformly randomly distributed among all (r · m, m)- homogeneous effective divisors. Moreover, the expected running time is polynomially bounded in m · r · d · log(q).

Proof. Before we come to the proof, we would like to caution the reader that it is incorrect to merely choose r prime divisors of degree m uniformly at random; this would not lead to a uniformly distributed output.

Let an instance as in the proposition be given.

An outline of the algorithm is as follows: First we compute a random vector \underline{μ} ∈ ℕ_{0}^{r} whose distribution is equal to the distribution of the multiplicity type of an effective divisor which is uniformly randomly distributed among all (r · m, m)-homogeneous divisors. Then we choose prime divisors of degree m P_{i,j} with i = 1, …, r and j = 1, …, μ_{i}, without repetition such that the tuple (P_{i,j})_{i,j} is uniformly distributed among all such tuples. We output the divisor ∑_{i=1}^{r} i · ∑_{j=1}^{μ_{i}} P_{i,j}. The output is then clearly uniformly distributed among all (r · m, m)-homogeneous divisors.

As for the details, we compute the P_{i,j} iteratively, discarding duplicates. The expected running time of this part of the computation is then as claimed. It remains to be shown that the vector \underline{μ} can be computed in the desired expected time.

The notion of multiplicity type immediately generalizes to arbitrary free abelian monoids, where previously we considered the free abelian monoid generated by prime divisors of degree m on C. And a free abelian monoid on a finite set P is the same as the set of multisets whose elements are in P (only the notation is different). As above, let B_{m} be the number of prime divisors of degree m on C. Then the multiplicity type of a multiset which is uniformly randomly distributed among all multisets of cardinality r and elements from {1, …, B_{m}} has the desired distribution. Now, the multisets of cardinality r with elements in {1, …, B_{m}} are in canonical bijection with the tuples (x_{1}, …, x_{r}) ∈ {1, …, B_{m}}^{r} with x_{i} ≤ x_{j} for i < j. These tuples are – as is well known – in bijection with the tuples (x′_{1}, …, x′_{r}) ∈ {1, …, B_{m} + r − 1} with x′_{i} < x′_{j} (via x′_{i} = x_{i} +i−1), and these are in bijection with the subsets of cardinality r of {1, …, B_{m} + r − 1}.

Note that B_{m} is part of the input. So, to compute the random vector \underline{μ}, we can proceed as follows: We choose a subset of cardinality r from {1, …, B_{m} + r − 1} uniformly at random. From this set, we compute the corresponding tuple (x_{1}, …, x_{r}) and then the multiplicity type of the corresponding multiset. Clearly, all this can be done in an expected time of (r · log(B_{m}))^{O(1)} ⊆ (r · m · log(q))^{O(1)}. □

Lemma 3.14 Given the L-polynomial of a curve of genus g over a finite field 𝔽_{q} and two natural numbers m ≤ n, one can compute the numbers ψ_{≤}(n, m), ψ_{=}(n, m) and ψ_{≥}(n, m) in a time which is polynomially bounded in n · g · log(q).

The proof of this lemma is inspired by the product formula for the zetafunction. The zeta-function is

∑_{i∈ℕ}A_{i}t^{i} = ∑_{D an eff. divisor} t^{deg D}

= ∏_{P a prime divisor}(1 − t^{deg(P)})^{−1} = ∏_{ℓ∈ℕ}(1 − t^{ℓ})^{−B_{ℓ}} .

Similarly, for all m ∈ ℕ,

∑_{i∈ℕ}ψ_{≤}(i, m)t^{i} = ∏_{ℓ≤m}(1 − t^{ℓ})^{−B_{ℓ}} ,  (16)

∑_{i∈ℕ}ψ_{=}(i, m)t^{i} = (1 − t^{m})^{−B_{m}} ,  (17)

and

∑_{i∈ℕ}ψ_{≥}(i, m)t^{i} = ∏_{ℓ≥m}(1 − t^{ℓ})^{−B_{ℓ}} .  (18)

The algorithm to compute ψ_{≤}(n, m) is as follows:

Let the L-polynomial L(t) be given. We first compute S_{1}, …, S_{m} via Newton’s identities (that is, via the equation L′(t) = −L(t) · (∑_{i=1}^{∞} S_{i}t^{i−1})) from the coefficients of the L-polynomial. From these we compute B_{1}, …, B_{m} using (11). Then we compute ∏_{ℓ≤m}(1 − t^{ℓ})^{B_{ℓ}} and the inverse of its residue class modulo t^{n+1}, which is ∑_{i=1}^{n} ψ_{≤}(i, m) [t]_{(t^{n+1})}^{i}.

The other algorithms operate similarly. □

Lemma 3.15 Given the L-polynomial of a curve g over a finite field 𝔽_{q} and natural numbers n, m with m ≤ n, one can with a randomized algorithm compute a random tuple \underline{e} ∈ ℕ_{0}^{n} with ∑_{ℓ} ℓe_{ℓ} = n whose distribution is equal to the distribution of the decomposition type of a random effective divisor on C which is uniformly distributed among all (n, m)-smooth divisors in an expected time which is polynomially bounded in g · n · log(q).

Proof. The algorithm operates in a recursive way and is based on partitioning the set of (n, m)-smooth divisors into subsets, according to how many prime divisors (with multiplicities) of degree m occur in an (n, m)-smooth divisor.

If m ≥ 2 and ℓ ∈ \{0, …, ⌊\frac{n}{m}⌋\}, there are

ψ_{=}(ℓm, m) · ψ_{≤}(n − ℓm, m − 1)

(n, m)-smooth divisors of the form ∑_{i=1}^{ℓ} P_{i} + D′, where the P_{i} are prime divisors of degree m and D′ is an m − 1-smooth divisor.

Algorithm for computation of a random tuple reflecting the distribution type of a random smooth divisor

Input: L, the L-polynomial of a curve over a finite field and two natural numbers n, m. (The algorithm is called by A(L, n, m)).

If m = 1, output (n, 0, …, 0) ∈ ℕ_{0}^{n}. Otherwise:

1. Compute ψ_{≤}(n, m) and the numbers a_{ℓ} ⟵ ψ_{=}(ℓm, m)·ψ_{≤}(n−ℓm, m− 1) for ℓ = 0, …, ⌊\frac{n}{m}⌋.

2. Let b_{ℓ} ⟵ ∑_{i=0}^{ℓ} a_{i} for ℓ = 0, …, ⌊\frac{n}{m}⌋; let b_{−1} ⟵ 0.

3. Choose a natural number x ≤ ψ_{≤}(n, m) uniformly at random.

4. Determine ℓ such that x ∈ [b_{ℓ−1} + 1, b_{ℓ}].

5. Output

(0, …, 0, ℓ, 0, …, 0) + (A(L, n − ℓm, m − 1) | \underline{0}) ∈ ℕ_{0}^{n} ,

where the non-trivial entry in the first tuple is at index m and (A(L, n − ℓm, m−1) | \underline{0}) is the concatenation of the output of the algorithm applied to L, n − ℓm, m − 1 and the zero-tuple of length ℓm.

By the remarks above the algorithm, the distribution of the random variable ℓ in Step 4 of the algorithm is equal to the distribution of the number of (n, m)-smooth divisors being the sum of ℓ prime divisors of degree m and an m − 1-smooth divisor.

It follows by induction on m that the algorithm operates correctly. Moreover, a running time as claimed can be achieved by Lemma 3.14. □

We now easily obtain:

Proposition 3.16 Given a curve C over a finite field 𝔽_{q}, represented by a plane model of degree d, as well as its L-polynomial, and a natural number n, one can with a randomized algorithm

• decide if there is an effective divisor of degree n on C

• compute a random effective divisor of degree n which is uniformly randomly distributed in the set of all effective divisors of degree n on C

in an expected time which is polynomially bounded in d · n · log(q).

Proof. The first statement is obvious because the L-polynomial is given.

Given the previous results, the algorithm for this proposition is straightforward: We compute a random tuple \underline{e} ∈ ℕ_{0}^{n} with ∑_{ℓ} e_{ℓ}ℓ = n whose distribution is equal to the distribution of the decomposition type of a random effective divisor on C which is uniformly distributed among all effective divisors of degree n.

Then for each ℓ = 1, …, n, we compute a uniformly randomly distributed (e_{ℓ}ℓ, ℓ)-homogeneous effective divisor D_{ℓ}.

We output the divisor ∑_{ℓ} D_{ℓ}.

By Proposition 3.13 and Lemma 3.15 these computations can be performed in the claimed expected running time. □

Proposition 3.17 Given a curve C over a finite field 𝔽_{q}, represented by a plane model of degree d as well as its L-polynomial and a divisor D_{0} of degree 1 whose height is polynomially bounded in d · log(q), one can with a randomized algorithm compute a uniformly randomly distributed element of Cl^{0}(C), represented by an along D_{0} reduced divisor, in an expected time which is polynomially bounded in d · log(q).

Proof. Every divisor D of degree ≥ 2g − 1 is non-special and thus the linear system |D| is isomorphic to ℙ^{deg(D)−g}(𝔽_{q}).

Therefore, if D is an effective divisor which is uniformly distributed among all divisors of some degree n ≥ 2g − 1, [D − deg(D) · D_{0}] is uniformly distributed in Cl^{0}(C). Moreover, 2g − 1 ≤ (d − 1)(d − 2) − 1.

In order to compute the desired uniformly distributed divisor class, we first compute a uniformly distributed effective divisor D of degree (d−1)(d− 2) − 1, and then we compute its reduction along D_{0}.

The computations can be performed in the claimed expected running time by the previous proposition and remarks in Section 2. □

We now prove:

Proposition 3.18 There exists a randomized algorithm such that the following holds: Given a curve C over a finite field 𝔽_{q}, represented by a plane model of degree d, as well as its L-polynomial and a divisor D_{0} of degree 1 whose height is polynomially bounded in d · log(q), the algorithm computes a system of elements c_{1}, …, c_{u} ∈ Cl^{0}(C), represented by along D_{0} reduced divisors, where u := eℓ with e := ⌈log_{2}(# Cl^{0}(C))⌉ and ℓ := ⌈log_{2}(e) + 1⌉. Moreover, the expected running time is polynomially bounded in d · log(q), and with a probability ≥ \frac{1}{2}, the system c_{1}, …, c_{u} is a generating system of Cl^{0}(C).

The proposition immediately follows from the preceding proposition and the following lemma (cf. the proof of [Heß05, Lemma 50]).

Lemma 3.19 Let G be a finite abelian group with N elements, let e := ⌈log_{2}(N)⌉, ℓ := ⌈log_{2}(e) + 1⌉, u := eℓ, and let g_{1}, …, g_{u} be uniformly distributed random elements of G. Then with a probability of ≥ \frac{1}{2}, g_{1}, …, g_{u} generate G.

Proof. To begin with, let H be a proper subgroup of G, and let g_{1}, …, g_{a} be uniformly randomly distributed elements from G. Then as \frac{#H}{#G} ≤ \frac{1}{2}, with a probability ≤ \frac{1}{2^{a}}, all g_{i} lie in H, that is, with a probability ≥ 1 − \frac{1}{2^{a}}, H ⊊ ⟨H, g_{1}, …, g_{a}⟩.

It follows by induction on b: Let a, b ∈ ℕ, and let g_{1}, …, g_{ab} be uniformly randomly distributed elements from G. Then with a probability ≥ (1 − \frac{1}{2^{a}})^{b} ≥ 1 − \frac{b}{2^{a}}, ⟨g_{1}, …, g_{a}⟩ contains at least min\{N, 2^{b}\} elements.

With b := e and a := ℓ, we have 2^{b} ≥ N and \frac{b}{2^{a}} ≤ \frac{1}{2}. The lemma thus follows. □

Proposition 3.2 follows from Proposition 3.18 and the fact – already mentioned in subsection 3.2 – that for curves of a bounded degree over finite fields, one can compute the L-polynomial in polynomially bounded time in log(q), where 𝔽_{q} is the ground field.

4 Index calculus for curves of lower-bounded genus

4.1 Overview

In order to establish Theorem 2, we combine algorithms for Theorem 1 with an algorithm for “sufficiently high genus curves”. For this second algorithm, we make use of some results from [Heß05], in particular a certain result on smoothness probabilities. We note that the result we need is merely an easy corollary of a result in [Heß05] which contains much more information if the genus of the curve is in a certain sense large against the bit-length of the cardinality of the ground field.

Outline of the proof

We give an outline of the proof of Theorem 2. Below we prove the following result.

Proposition 4.1 Let C > 0 be fixed. Then there exists some g_{1} ∈ ℕ such that one can solve the discrete logarithm problem in the degree 0 class groups of curves of genus ≥ g_{1} in an expected time of O((q^{g})^{C}), where q is the cardinality of the ground field and g is the genus.

We show now how one can obtain Theorems 2 via this result and Theorem 1. We first consider the second statement in Theorem 2.

Let g_{0} be a natural number ≥ 2, and let C := \frac{2}{g_{0}} (1 − \frac{1}{g_{0}} ). Let g_{1} be as in the proposition for this constant C.

Then given an instance of the discrete logarithm problem with a curve of genus g ≥ g_{0}, we first compute its genus g. Then we proceed with a case distinction. If the genus is ≥ g_{1} we apply an algorithm which satisfies Proposition 4.1. If the genus is < g_{1}, we apply an algorithm which satisfies Theorem 1 for genus g curves.

We now come to the first statement in Theorem 2. By the lower bound on # Cl^{0}(C) from [LMD90] stated in Section 2 (Equation (2) on page 9), q^{g} is in Õ(# Cl^{0}(C)). The second statement in Theorem 2 therefore immediately also gives the first statement.

4.2 The algorithm

We now outline an algorithm for Proposition 4.1, accompanied by statements on running times. The algorithm is substantially easier to state than the index calculus algorithm in Section 3: It is a ”basic” index calculus algorithm without large prime variation. The algorithm is closely related to the algorithms in [Heß05], and we make use of various results from [Heß05].

For the index calculus algorithm we again need a generating system. We could proceed as in Section 3: Using a very small system which with probability ≥ \frac{1}{2} is a generating system and terminating the algorithm if a predefined time bound is reached. However, in the situation we are concerned with here, there is an easier solution: It is shown in [Heß05] that one can compute a generating system of a size which is polynomially bounded in q · g in an expected time which is also polynomially bounded in q · g (see [Heß05, Theorem 34 and Algorithm 35]).

Note that generally if any subroutine of our algorithm has an expected running time which is polynomially bounded in q · g, then this subroutine in particular has an expected running time of O(q^{Cg}) for g large enough. Thus if such a subroutine is executed once or even a number of times which is polynomially bounded in q · g, then the running time of this subroutine is not critical for the establishment of the desired result.

In the algorithm, we again first compute the group order N and factor it. We fix an appropriate smoothness bound S and define the factor base as the set of prime divisors on C of degree ≤ S. After this, we generate a relation matrix. Here we follow Step 4 of the algorithm for Theorem 1; generating the relations in a different way however. After this, we proceed as in the algorithm for Theorem 1.

We now describe the important steps of the algorithm.

Obviously, we only have to establish Proposition 4.1 for constants C of the form C = \frac{1}{c} for c ∈ ℕ. So let c ∈ ℕ be fixed, and let C := \frac{1}{c}.

As usual, let us fix an instance consisting of a curve C/𝔽_{q}, a divisor D_{0} of degree 1, a, b ∈ Cl^{0}(C) with b ∈ ⟨a⟩ and a generating system c_{1}, …, c_{u}.

Computation of the group order and factorization

A. Lauder and D. Wan have shown in [LW08] that one compute the order of the degree 0 class group of a curve over 𝔽_{q} given by a plane model of degree d in a time which is polynomially bounded in q · d. (In fact, if q = p^{e} with p prime and n ∈ ℕ, the running time is polynomially bounded in p · e · d.) Note that as by our assumption d ∈ O(g), the running time is in particular polynomially bounded in q · g.

The order can be factored in subexponential time in # Cl^{0}(C) (cf. [Pom87]). This implies that it can be factored in subexponential time in q^{g} too. Therefore this computation is not time critical.

Construction of the factor base

We first compute the genus g. We fix a ”smoothness bound” m := ⌈\frac{g}{8c}⌉, and let the factor base F be the set of prime divisors of degree ≤ m. Here we construct the set of prime divisors by iterating over all prime divisors of degree ≤ m on ℙ_{𝔽_{q}}^{1} and considering the preimages under the covering x : C ⟶ ℙ_{𝔽_{q}}^{1}.

The factor base has ≤ r · (q + 1)^{m} elements, where r := deg(x). For g ≥ 8c, we have m ≤ \frac{g}{4c}. As furthermore r ≤ d ∈ O(g), the size of the factor base is then (for g ≥ 8c) in Õ(q^{\frac{g}{4c}}), and the expected running time is also in Õ(q^{\frac{g}{4c}}).

Relation generation

Let t ∈ ℕ be defined as in the algorithm for Theorem 1. Now as in the algorithm for Theorem 1, we generate relations in two different ways: First we generate (k+2u)·t relations as follows: We choose α, β, s_{1}, …, s_{u} ∈ ℤ/Nℤ uniformly at random and choose uniformly randomly a divisor D in the class s_{1}c_{1} + ⋯ + s_{u}c_{u} + αa + βb + (2g − 1) · [D_{0}]. Second for i_{1} = 1, …, k, we generate t relations by again choosing α, β, s_{1}, …, s_{u} ∈ ℤ/Nℤ uniformly at random and choosing uniformly randomly a divisor D in the class [F_{i_{1}}] − [D_{0}] + s_{1}c_{1} + ⋯ + s_{u}c_{u} + αa + βb + (2g − 1) · [D_{0}]. In any case, if D is m-smooth, we have obtained a relation between input elements and factor base elements.

Each iteration can be performed in an expected time of (g log(q))^{O(1)} · u. Note also that as the random divisor class s_{1}c_{1} + ⋯ + s_{u}c_{u} + αa + βb + (2g − 1)[D_{0}] is uniformly distributed in the set of divisor classes of degree 2g − 1 and divisors of degree ≥ 2g − 1 are non-special, the random divisor D is uniformly distributed in the set of all effective divisors of degree 2g − 1.

In order to bound the expected running time for the generation of one relation between input elements and factor base elements, we need a lower bound on the probability that a uniformly distributed random divisor of degree 2g − 1 is m-smooth. For this we can use [Heß05, Theorem 8] which gives a much more precise statement than the one we need. In fact, just from the fact that m ∈ Ω(2g − 1), we learn from [Heß05, Theorem 8] that the probability in question is in \frac{1}{g^{Ω(1)}} .

This establishes that the expected running time needed to generate one relation is in (g · log(q))^{O(1)} · u, and the total expected time to generate the relation matrix is therefore in (g · log(q))^{O(1)} · u · Õ(#F). For g ≥ 8c (such that the size of the factor base is in Õ(q^{\frac{g}{4c}})) this is contained in (g · log(q))^{O(1)} · u · Õ(q^{\frac{g}{4c}}).

For g large enough, the expected time for the construction of the relation matrix is then in Õ(q^{\frac{g}{2c}}), as is the number of non-trivial entries.

Linear algebra

We use an algorithm from sparse linear algebra, as in the previous algorithm. For g large enough the linear algebra then takes an expected time of Õ(q^{\frac{3g}{4c}})

Final result

We see that for g large enough, the expected running time is in O(q^{\frac{g}{c}}).

5 Index calculus for elliptic curves over extension fields of a fixed degree

5.1 Overview

In this section we establish Theorem 3. The algorithm is closely related to the algorithm for Theorem 1, and the structures of the algorithms are the same. The key differences concern the definition of the factor base and the relation generation.

In subsection 5.3 we give an index calculus algorithm with double large prime variation which leads to the following proposition. We alert the reader to the similarity with Proposition 3.1.

Proposition 5.1 Let us fix some n ≥ 2. Then there exists a randomized algorithm such that the following holds: Upon input of an elliptic curve E/𝔽_{q^{n}}, elements A, B ∈ E(𝔽_{q^{n}}) with B ∈ ⟨A⟩ and a system C_{1}, …, C_{u} of elements of E(𝔽_{q^{n}}), if the algorithm terminates, it outputs the discrete logarithm of B with respect to A. Moreover, if C_{1}, …, C_{u} forms a generating system of E(𝔽_{q^{n}}) and u is polynomially bounded in log(q), the expected running time of the algorithm is in Õ(q^{2− \frac{2}{n}}).

The algorithm uses only the first Õ(q^{1− \frac{1}{n} + \frac{1}{n^{2}}} ) registers, and each register always contains elements whose bit-length is polynomially bounded in log(q).

Together with the arguments in Section 3 this proposition establishes Theorem 3.

The algorithm for this proposition is also quite similar to the algorithm for Proposition 3.1. The only essential difference is that we define the factor base and generate the relations is a different way.

Briefly, the factor base is defined as follows: We fix a covering φ : E ⟶ ℙ_{𝔽_{q}}^{1} of degree 2 satisfying a certain condition which is stated below (Condition 5.8). Then the factor base is some subset of {P ∈ E(𝔽_{q^{n}}) | φ(P) ∈ ℙ^{1}(𝔽_{q})\} consisting of ⌈q^{1− \frac{1}{n}} ⌉ or ⌈q^{1− \frac{1}{n}} ⌉ + 1 elements.

Relations are generated by what we call a decomposition algorithm. This algorithm relies on solving systems of multivariate polynomial equations over 𝔽_{q}. The systems are derived from so-called summation polynomials.

In the next subsection we give some background information and specify what exactly we mean by a decomposition algorithm, following [Die10]. We also give the key result for the analysis of the algorithm in the present situation. More information and proofs can be found in [Die10]. Then in subsection 5.3 we discuss the index calculus algorithm.

5.2 The decomposition algorithm

The key properties on the summation polynomials we need are stated in the following two propositions.

Proposition 5.2 Let E be an elliptic curve over a field k, and let us fix a covering φ : E ⟶ ℙ_{k}^{1} of degree 2 with φ ∘ [−1] = φ. Let m ∈ ℕ with m ≥ 2. Then there exists an up to multiplication by a non-trivial constant unique irreducible multihomogeneous polynomial S_{φ,m} ∈ k[X_{1}, Y_{1}, X_{2}, Y_{2}, …, X_{m}, Y_{m}] such that for all P_{1}, …, P_{m} ∈ E(\overline{k}) we have S_{φ,m}(φ(P_{1}), …, φ(P_{m})) = 0 ⟷ ∃ϵ_{1}, …, ϵ_{m} ∈ {1, −1} such that ϵ_{1}P_{1} + ⋯ ϵ_{m}P_{m} = O. The polynomial S_{φ,m} has multidegree (2^{m−2}, …, 2^{m−2}).

Definition 5.3 We call a multihomogeneous polynomial S_{φ,m} as in the proposition an m^{th} summation polynomial of E with respect to φ.

Remark 5.4 The summation polynomials introduced here are the “homogenized variants” of the summation polynomials in [Sem04].

Proposition 5.5 Given an elliptic curve in Weierstraß form over a finite field 𝔽_{q} m ∈ ℕ with m ≥ 2 and φ : E ⟶ ℙ_{k}^{1} of degree 2 with φ ∘ [−1] = φ, the m^{th} summation polynomial with respect to the covering φ : E ⟶ ℙ_{𝔽_{q}}^{1} can be computed with a randomized algorithm in an expected time which is polynomially bounded in e^{m^{2}} · log(q).

Note that for fixed m the expected running time is polynomially bounded in log(q).

These two propositions are [Die10, Proposition 2.1] and [Die10, Proposition 2.3].

Now let K|k be a field extension of degree n with basis b_{1}, …, b_{n}, let E be an elliptic curve over K (rather than over k!), and let φ : E ⟶ ℙ_{K}^{1} be a covering of degree 2 with φ ∘ [−1] = φ.

Now let P ∈ E(K). Let S_{φ,n+1}(X_{1}, Y_{1}, …, X_{n}, Y_{n}, φ(P)) be a polynomial obtained by inserting the coordinates of φ(P) for the variables X_{n+1}, Y_{n+1} in an (n + 1)^{th} summation polynomial of E with respect to φ; note that this polynomial is unique up to multiplication with a non-trivial constant.

Let S^{(1)}, …, S^{(n)} ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}] be defined by

∑_{j=1}^{n} b_{j}S^{(j)} = S_{φ,n+1}(X_{1}, Y_{1}, …, X_{n}, Y_{n}, φ(P)) .  (19)

Clearly, if S^{(j)} is non-zero, just as S_{φ,n+1} it is multigraded of multidegree (2^{n−1}, …, 2^{n−1}). Note also that a different basis of K|k would give rise to a system of polynomials over k which generate the same k-vector space. The same holds if the summation polynomial is multiplied by a non-trivial constant or if the coordinates of φ(P) are simultaneously multiplied by a non-trivial constant. In particular, the subscheme V (S^{(1)}, …, S^{(n)}) of (ℙ_{k}^{1})^{n} does not depend on these choices.

For Q_{1}, …, Q_{n} ∈ ℙ^{1}(k), the following conditions are equivalent:

• There exist P_{1}, …, P_{n} ∈ E(\overline{K}) such that P_{1} + ⋯ + P_{n} = P and x(P_{i}) = Q_{i} for all i = 1, …, n.

• S_{φ,n+1}(Q_{1}, …, Q_{n}, φ(P)) = 0.

• For all j = 1, …, n, S^{(j)}(Q_{1}, …, Q_{n}) = 0, that is, (Q_{1}, …, Q_{n}) is a k-rational point of V (S^{(1)}, …, S^{(n)}).

Definition 5.6 A tuple (P_{1}, …, P_{n}) ∈ E(K)^{n} with P_{1} + ⋯ + P_{n} = P and φ(P_{i}) ∈ ℙ^{1}(k) for i = 1, …, n is called a decomposition of P with respect to φ. Let such a decomposition be given and let Q_{i} := φ(P_{i}). If now (Q_{1}, …, Q_{n}) is an isolated point of V (S^{(1)}, …, S^{(n)}), the decomposition is called φ-isolated.

The “decomposition problem” is now the following computational problem: Given a prime power q, n ∈ ℕ, an 𝔽_{q}-basis b_{1}, …, b_{n} of 𝔽_{q^{n}}|𝔽_{q}, an elliptic curve E over 𝔽_{q^{n}} (given by a Weierstraß model), φ : E ⟶ ℙ_{k}^{1} as well as P ∈ E(𝔽_{q^{n}}) of degree 2 with [−1] ∘ φ = φ, output a list of decompositions of P with respect to φ containing all φ-isolated decompositions. A “decomposition algorithm” is then a randomized algorithm for this problem. By [Die10, Proposition 2.6] we have:

Proposition 5.7 There exists a decomposition algorithm which operates in an expected time of Poly(e^{n^{2}} · log(q)). For fixed n the expected running time is therefore polynomially bounded in log(q).

We need a lower bound on the probability that a a uniformly randomly distributed point has a φ-isolated decomposition. For this, we impose the following condition on the covering φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} with deg(φ) = 2 and φ ∘ [−1] = φ is:

Condition 5.8 There exists a point P ∈ ℙ^{1}(\overline{𝔽}_{q}) which is a ramification point of φ such that the points P, σ(P), …, σ^{n−1}(P) are all distinct and φ is not ramified at σ(P), …, σ^{n−1}(P).

The key result for the analysis of the algorithm is now:

Proposition 5.9 Let n be fixed. Then again for elliptic curves E/𝔽_{q^{n}} and coverings φ such that Condition 5.8 holds the following is true:

a) #{P ∈ E(𝔽_{q^{n}}) | φ(P) ∈ ℙ^{1}(𝔽_{q})} ∼ q.

b) There exist constants C, D > 0 such that the following holds: Let M be any subset of {(P_{1}, …, P_{n}) ∈ E(𝔽_{q^{n}})^{n} | φ(P_{i}) ∈ ℙ^{1}(𝔽_{q}) for all i = 1, …, n}. Then the number of elements P ∈ E(𝔽_{q^{n}}) such that there exists a φ-isolated decomposition (P_{1}, …, P_{n}) of ±P with P_{1}, …, P_{n} ∈ M is

≥ D · #M − C · q^{n−1} .

Part a) of this result follows from [Die10, Proposition 4.10]. Part b) is a summary of [Die10, Proposition 4.28] for fixed n.

5.3 The index calculus algorithm

Let n ≥ 2 be fixed. We now describe the index calculus algorithm leading to Proposition 5.1.

As already mentioned the algorithm has the same structure as the algorithm in subsection 3.2. So we describe the necessary modifications.

Let E/𝔽_{q^{n}}, A, B, C_{1}, …, C_{u} ∈ E(𝔽_{q^{n}}) with B ∈ ⟨A⟩ be given.

Step 1 – Computation of the group order and factorization

We can now use Schoof’s algorithm ([Sch85]) to compute N = #E(𝔽_{q^{n}}). Of course, the running time of Step 1 is still subexponential in log(q).

Step 2 – Construction of the factor base

We choose φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} satisfying Condition 5.8. By [Die10, Proposition 2.8] except if (q, n) ≠ (3, 2) such a covering exists, and moreover it can be constructed in an expected time which is polynomially bounded in log(q). We enumerate the set {P ∈ E(𝔽_{q^{n}}) | φ(P) ∈ ℙ^{1}(𝔽_{q})}.

Then we fix some subset F of cardinality ⌈q^{1− \frac{1}{n}} ⌉ or ⌈q^{1− \frac{1}{n}} ⌉ + 1 of \{P ∈ E(𝔽_{q^{n}}) | φ(P) ∈ ℙ^{1}(𝔽_{q})} which is invariant under application of [−1]. (Note that for q large enough this is possible by Proposition 5.9.) The set of large primes is then L := {E(𝔽_{q^{n}}) | φ(P) ∈ ℙ^{1}(𝔽_{q}), P ∉ F}.

Clearly these operations can be performed in an expected time of Õ(q).

Step 3 – Generation of the tree of large prime relations

The construction tree of large prime relations is performed as in subsection 3.2, only that we now use the decomposition algorithm. A minor difference is that we do not anymore have unique factorization, and we check for each output of the decomposition algorithm if it leads to a useful FP or PP relation. The procedure is therefore as follows:

Procedure: Construction of the tree of large prime relations

Construct a labeled rooted tree T with vertex set contained in L ˙∪ {∗} as follows: Let T consist only of the root ∗, labeled with 0. Let N_{max} ⟵ ⌈q^{1−1/n+1/n^{2}}⌉ Let s ⟵ 1. Repeat

Repeat Choose s_{1}, …, s_{u} ∈ ℤ/Nℤ uniformly and independently at random. Apply a decomposition algorithm to ∑_{j} s_{j}C_{j}; let L be the output of the algorithm. Check for every tuple (P_{1}, …, P_{n}) ∈ L if it leads to a relation of the form

∑_{j} r_{j}F_{j} + Q = ∑_{j} s_{j}C_{j}

where Q ∈ L − (F ∪ T) (“useful FP relation”)

or

∑_{j} r_{j}F_{j} + r_{P} P + Q = ∑_{j} s_{j}C_{j}

where r_{P} > 0, P ∈ T_{s−1} and Q ∈ L−(F ∪T) (“useful PP relation”). If this is the case,

fix such a relation.

If we have a “useful FP relation”,

insert Q and an edge from ∗ to Q into T if we have a “useful PP relation”,

insert Q and an edge from P to Q into T. In both cases label Q with s and the edge with (r_{j})_{j} (in sparse representation).

Until T contains 2^{s−1} ·⌈q^{1−1/n}⌉ edges or the number of edges equals N_{max}. If the number of edges equals N_{max}, STOP. Let s ⟵ s + 1.

Here as in subsection 3.2 T_{s} is the subtree of T consisting of vertices with label ≤ s, that is, the tree which is constructed until including stage s.

With part b) of Proposition 5.9 the analysis in subsection 3.3 carries also easily over to the present setting. Let us first consider Stage 1 of the algorithm, that is, s = 1.

We set

M := F^{n−1} × (L − T) .

For q large enough (independently of T) this set has cardinality ≥ (q^{1− \frac{1}{n}})^{n−1}· \frac{q}{4}. Therefore the number of elements in E(𝔽_{q^{n}}) for which we obtain a new edge is ≥ \frac{D}{4} · (q^{1− \frac{1}{n}})^{n−1} · q − C · q^{n−1} = \frac{D}{4} · q^{n−1+ \frac{1}{n}} − Cq^{n−1}. For q large enough this is

≥ \frac{D}{8} · q^{n−1+ \frac{1}{n}} ,

and again for q large enough, the probability that one try (one iteration of the inner Repeat-loop) leads to a new edge is therefore

≥ \frac{D}{16} · q^{−(1− \frac{1}{n})} .

Thus for q large enough, the expected number of tries until a tree of size ⌈q^{1− \frac{1}{n}} ⌉ is constructed is

≤ \frac{D}{16} · (q + 1)^{2− \frac{2}{n}} .

Let us now assume that we are in Stage s with s ≥ 2. We set

M := F^{n−2} × (F ∪ T_{s−1}) × (L − T) .

Now for q large enough (and independently of T, in particular independently of s) this set has cardinality ≥ (q^{1− \frac{1}{n}})^{n−2}·2^{s−2}·q^{1− \frac{1}{n}} · \frac{q}{4} = 2^{s−2}·(q^{1− \frac{1}{n}})^{n−1}· \frac{q}{4}. For q large enough the probability to obtain a new edge is

≥ \frac{D}{16} · 2^{s−2} · q^{−(1− \frac{1}{n})} .

This implies that for q large enough (independently of s) the following holds: Given any tree T with 2^{s−2} ·⌈q^{1− \frac{1}{g}} ⌉ edges, the expected number of tries until a tree T with min\{2^{s−1} · ⌈q^{1− \frac{1}{n}} ⌉, N_{max}\} edges is constructed is

≤ \frac{32}{D} · (q + 1)^{2− \frac{2}{n}} .

This completes the analysis.

Step 4 – relation generation

The relation generation is also as in subsection 3.2, again with the obvious difference that we use the decomposition algorithm. Again by item b) of Proposition 5.9 it is obvious that the expected running time is in Õ(q^{2− \frac{2}{n}}).

Steps 5 – 7 are as in the original algorithm.

The overall running time and conclusion

Altogether we obtain an expected running time of Õ(q^{2− \frac{2}{n}}), and we have storage requirements of Õ(q^{1− \frac{1}{n} + \frac{1}{n^{2}}} ), as indicated in Proposition 5.1.

References

[AHU74] A. Aho, J. Hopcroft, and J. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974.

[Coh96] H. Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1996.

[Die08] C. Diem. On arithmetic and the discrete logarithm problem in class groups of curves, 2008. Habilitation thesis.

[Die10] C. Diem. On the discrete logarithm problem in elliptic curves. Accepted for publication at Compos. Math., 2010.

[EG02] A. Enge and P. Gaudry. A general framework for subexponential discrete logarithm algorithms. Acta. Arith., 102:83–103, 2002.

[Gau09] P. Gaudry. Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symbolic Computation, 44:1690–1702, 2009.

[GTTD07] P. Gaudry, E. Thomé, N. Thériault, and C. Diem. A double large prime variation for small genus hyperelliptic index calculus. Math. Comp., 76:475–492, 2007.

[Heß01] F. Heß. Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symb. Comput., 11, 2001.

[Heß05] F. Heß. Computing relations in divisor class groups of algebraic curves over finite fields. preprint, ca. 2005.

[LMD90] G. Lachaud and M. Martin-Deschamps. Nombre de points des jacobiennes sur un corps fini. Acta. Arith., 56:329–340, 1990.

[LW08] A. Lauder and D. Wan. Counting points on varieties over finite fields of small characteristic. In J. Buhler and P. Stevenhagen, editors, Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. Cambridge University Press, 2008.

[Nag07] K. Nagao. Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes. Japan J. Indust. Appl. Math., 24, 2007.

[Pil90] J. Pila. Frobenius maps of abelian varieties and fining roots of unity in finite fields. Math. Comp., 55:745–763, 1990.

[Pil91] J. Pila. Counting points on curves over families in polynomial time. Available on the arXiv under math.NT/0504570, 1991.

[Pom87] C. Pomerance. Fast, rigorous factorization and discrete logarithm algorithms. In D. Johnson, T. Nishizeki, A. Nozaki, and H. Wolf, editors, Discrete Algorithms and Complexity, Proceedings of the Japan US Joint Seminar, June 4-6, 1986, Kyoto, Japan, pages 119–143, 1987.

[RS62] J. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math., 6(64-94), 1962.

[Sch85] R. Schoof. Elliptic curves over finite fields and the compuation of square roots mod p. Math. Comp., 44:483–494, 1985.

[Sem04] I. Semaev. Summation polynomials and the discrete logarithm problem on elliptic curves. available under http://eprint.iacr.org/2004/031, Feb. 2004.

[Sti93] H. Stichtenoth. Algebraic Function Fields and Codes. Springer-Verlag, 1993.