On the discrete logarithm problem for plane curves

Claus Diem

October 26, 2012

Abstract In this article the discrete logarithm problem in degree 0 class groups of curves over finite fields given by plane models is studied. It is proven that the discrete logarithm problem for non-hyperelliptic curves of genus 3 (given by plane models of degree 4) can be solved in an expected time of Õ(q), where q is the cardinality of the ground field. Moreover, it is proven that for every fixed natural number d ≥ 4 the following holds: We consider the discrete logarithm problem for curves given by plane models of degree d for which there exists a line which defines a divisor which splits completely into distinct 𝔽_{q}-rational points. Then this problem can be solved in an expected time of Õ(q^{2− \frac{2}{d−2}} ). This holds in particular for curves given by reflexive plane models.

1 Introduction

This article is concerned with the complexity of the discrete logarithm problem in degree 0 class groups of curves over finite fields. (Unless stated otherwise, a curve is always assumed to be proper, non-singular and geometrically irreducible.) In various works on the subject, the complexity of the computation is expressed in terms of the genus and the cardinality of the ground field. For example, it is proven in [3] that for any fixed g ∈ ℕ, 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}}) .  (1)

Here and in the following, q is the cardinality of the ground field. We note that as usual, throughout this article the phrase “expected time” refers to the internal randomizations of an algorithm. Randomizations over input instances are not considered.

In this article, we study the complexity of the problem from a different point of view: We assume that the curve is given by a plane model, by which we mean a possibly singular plane curve which is birational to the curve in question. We then express the complexity in terms of the degree of the model and the cardinality of the ground field.

Our first result concerns non-hyperelliptic genus 3 curves. Via the canonical embedding, every such curve can be given as a plane curve of degree 4. By using such a model, we obtain the following result:

Theorem 1 The discrete logarithm problem in the degree 0 class groups of non-hyperelliptic curves of genus 3 can be solved in an expected time of Õ(q).

For comparison, the expected running time indicated in (1) is Õ(q^{\frac{4}{3}} ) in this case.

To state our second result, we need some notation: First, we set ℙ_{𝔽_{q}}^{2} := Proj(𝔽_{q}[X, Y, Z]). Let C be a curve over 𝔽_{q}, C_{pm} a plane model of C and π : C ⟶ C_{pm} a birational morphism. Let O_{C}(1) := π^{∗}(O(1)), and for a linear form W ∈ 𝔽_{q}[X, Y, Z]_{1} = Γ(ℙ_{𝔽_{q}}^{2}, O(1)) let W_{|C} := π^{∗}(W) ∈ Γ(C, O_{C}(1)). Let div(W_{|C}) = π^{∗}(div(W)) be the divisor of zeroes of W_{|C} on C. Now let 𝔡 be the linear system on C “cut out by lines” (more precisely: obtained by pull-back of lines), that is,

𝔡 := { div(W_{|C}) | W ∈ 𝔽_{q}[X, Y, Z]_{1} = Γ(ℙ_{𝔽_{q}}^{2}, O(1)) } .

This is a 2-dimensional projective subspace of the complete linear system defined by O_{C}(1).

We say that an effective divisor splits completely if its support contains only 𝔽_{q}-rational points.

The second result is as follows:

Theorem 2 Let d ≥ 4 be fixed. Then the discrete logarithm problem in the degree 0 class groups of curves given by plane models of degree d such that the linear system 𝔡 contains a divisor which splits completely into distinct points can be solved in an expected time of

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

We also show the following theorem on curves given by plane models, a result we consider to be of independent interest.

Theorem 3 Let d ≥ 3 be fixed. We consider curves of genus at least one given by plane models of degree d, where for d > 4 we restrict ourselves to reflexive plane models. Then the number of divisors in 𝔡 which split completely into distinct points is in \frac{1}{d!}q^{2} + O(q^{\frac{3}{2}} ).

Briefly, reflexivity means that the classical duality theory holds. We note that for characteristic 2, no plane model is reflexive, and if the degree is larger than the characteristic, every plane model is reflexive. More information on the notion of reflexivity can be founded below.

Theorems 2 and 3 give:

Theorem 4 Let d ≥ 4 be fixed. Then the discrete logarithm problem in the degree 0 class groups of curves given by reflexive plane models of degree d can be solved in an expected time of

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

Let us consider curves of a fixed genus g given by plane models of a fixed degree d such that 𝔡 contains a divisor which splits completely into distinct points. Then under the condition that g ≥ d − 1, the expected running time in the second theorem improves upon one of [3], mentioned in (1) above. The algorithms then have storage requirements of Õ(q^{1− \frac{1}{g} + \frac{1}{(d−2)·g}}).

The underlying computational model is throughout a randomized random access machine with logarithmic cost function. We refer the reader to [4] for a discussion on random access machines.

Reflexive plane models

We briefly review the notion of reflexivity and give some characterizations of a plane model being reflexive.

Let k be some field which for the moment we assume to be algebraically closed. Let X be an irreducible closed subvariety of ℙ_{k}^{n}, and let X_{ns} be the non-singular (=smooth) part of X. Let ℙ_{k}^{n∗} be the dual space of ℙ_{k}^{n}. The conormal variety C(X) ⊆ ℙ_{k}^{n} ×ℙ_{k}^{n∗} of X is the closure of pairs (P, H), where P is a closed point of X_{ns} and H is a hyperplane of ℙ_{k}^{n} which meets X in P tangentially. The dual variety X^{∗} of X is the image of C(X) in ℙ_{k}^{n∗}. Analogous definitions can be made for subvarieties of ℙ_{k}^{n∗}. Now X is called reflexive if – up to change of factors of ℙ_{k}^{n} × ℙ_{k}^{n∗} and identification of ℙ_{k}^{n∗∗} with ℙ_{k}^{n} – C(X) = C(X^{∗}). Reflexive varieties are (trivially) bidual, that is, X^{∗∗} = X. In characteristic 0, every closed subvariety of ℙ_{k}^{n} is reflexive, but this is not anymore the case if the characteristic is positive.

We are interested in the case that n = 2 and X is one-dimensional and not a line. Let these conditions be satisfied. The canonical projection C(X) ⟶ X is now birational. Let ρ : C(X) ⟶ X^{∗} be the canonical map to the dual variety. If X is reflexive, then just as the projection to X, the morphism ρ is birational too. Moreover, the following conditions are equivalent:

1. X is not reflexive.

2. ρ is not birational.

3. ρ^{∗} : k(X^{∗}) ⟶ k(C(X)) is inseparable.

4. For sufficiently general pairs (P, H), where P is a closed point on X and H is a hyperplane which meets C in P tangentially, the intersection number of H and X at P is equal to the degree of inseparability of ρ^{∗}.

5. The characteristic of k is 2 or for sufficiently general pairs (P, H), where P is a closed point on C and H is a hyperplane which meets X in P tangentially, the intersection number of H and X at P is > 2.

6. Let F (X_{1}, X_{2}, X_{3}) be a defining homogeneous polynomial of X, that is, X = V (F). Then all polynomials F_{i}^{2}F_{jj} + F_{j}^{2}F_{ii} − 2F_{i}F_{j}F_{ij} for i, j = 1, 2, 3 vanish on X. Here for a polynomial f ∈ k[X_{1}, X_{2}, X_{3}] and i = 1, 2, 3, f_{i} = \frac{∂f}{∂X_{i}}.

The equivalence of the first and the third statement (and thus with the second too) goes back to [19] and is called the Segre-Wallace criterion; for a modern proof see [11, Theorem 4]. The equivalence of these statements with the forth one is established in [9] and called the generic order of contact theorem there. The equivalence with the last two statements can be found in [8] (see Remark 4.5 and Proposition 4.12 there).

By the fifth (or sixth) statement, if char(k) = 2, then X cannot be reflexive. Other examples of non-reflexive varieties in the projective plane are the so called strange curves, that is, one-dimensional irreducible varieties whose tangents all pass through a common point. In this case the dual variety is a line and the bidual is a point.

Moreover, by the forth statement, if char(k) > deg(X), then X is reflexive.

Let now k be a perfect field and let X be a geometrically irreducible and geometrically reduced closed subvariety of ℙ_{k}^{n}. Then C(X\overline{k}), (X\overline{k})^{∗} and ρ are invariant under the action of the absolute Galois group of k. The varieties thus descend to k as subvarieties of the corresponding surrounding spaces, and ρ descends too. In case that n = 2 and X is one-dimensional and not a line, the statements (1), (2), (3) and (6) are then still equivalent. We call X reflexive if these conditions are satisfied.

Notation and representation

We fix some notation we use throughout the article, and we discuss the representation of the basic objects for algorithmic purposes.

As already mentioned, the input curve C/𝔽_{q} is represented by a plane model C_{pm} in ℙ_{𝔽_{q}}^{2} of a fixed degree d ≥ 4. Concretely, we assume that C_{pm} (and therefore also C) is given by a homogeneous polynomial F (X, Y, Z) ∈ 𝔽_{q}[X, Y, Z].

So, to the polynomial F (X, Y, Z) we associate C_{pm}, the variety defined by F (X, Y, Z), and to C_{pm} we associate its normalization, which is a (nonsingular) curve C together with a birational morphism π : C ⟶ C_{pm}. We also denote the composition of π with the inclusion C_{pm} ↪ ℙ_{𝔽_{q}}^{2} by π. Moreover, we denote the non-singular part of C_{pm} by C_{ns} (rather than by (C_{pm})_{ns}), and we identify C_{ns} with its preimage in C. We call the dual variety of C_{pm} the dual model and denote it by C_{pm}^{∗}.

To represent divisors on C, we use an ideal theoretic representation, following [10]. Recall that in [10] divisors are represented by ideals of two orders of the function field of C: a so-called finite and a so-called infinite order. We call this the joint ideal representation. Alternatively, one can use the free ideal representation, where the prime divisors are represented by prime ideals of these orders and the ideals themselves are represented by formal sums of the prime divisors (in sparse representation).

For q large enough, C has an 𝔽_{q}-valued point. Let P_{0} be such a point. An effective divisor D on C is called reduced along P_{0} if the complete linear system |D − P_{0}| is empty. One sees easily that for any divisor class c there exists a unique along P_{0} reduced effective divisor D with c = [D] + (deg(c) − deg(D)) · [P_{0}].

For the representation of divisor classes, we fix a point P_{0} and represent a divisor class c by the corresponding reduced effective divisor and the degree. This applies in particular to the input elements.

For more information on these issues, in particular on computational aspects, we refer to [10], [2, Chapter 2] and [3, Section 2].

The following definitions will be convenient in the analysis of the algorithm:

First, the usual definitions of limit and limes inferior can be immediately extended from real valued sequences over the natural numbers to real valued sequences over any countable infinite set 𝕏. We make use of these extensions. Moreover, for a function (i.e., sequence) f : 𝕏 ⟶ ℝ_{>0} we have the usual sets O(f), Õ(f), Ω(f) and Θ(f) of sequences on X. We do not use the usual “Landau notation” like g = O(f) but use the usual set-theoretic notation g ∈ O(f) instead.

We fix the following definition.

Definition 1 Let 𝕏 be an infinite countable set and (a_{x})_{x∈𝕏} ∈ ℝ^{𝕏}, (b_{x})_{x∈𝕏} ∈ ℝ_{>0}^{𝕏}. Then we write

a_{x} ≳ b_{x}

if lim inf_{x∈𝕏} \frac{a_{x}}{b_{x}} ≥ 1.

In our applications, the elements of 𝕏 consist of isomorphism classes of the following data: a curve C/𝔽_{q}, a plane model C_{pm} of the curve, a birational morphism π : C ⟶ C_{pm} and additionally a tuple of points in C(𝔽_{q}) or a subset S ⊆ C(𝔽_{q}) (or both). Isomorphisms are isomorphisms of curves over 𝔽_{q} respecting the maps to the projective plane and additionally the points or the subset.

Let such a set 𝕏 be fixed. For some element x ∈ 𝕏 let q_{x} be the cardinality of the ground field. If for some prime power q and some x ∈ 𝕏 we have q_{x} = q, we say that x is over 𝔽_{q}.

We will consider such sets 𝕏 with the property that for every prime power q there are only finitely many elements over q. Let 𝕏 be such a set, and let (a_{x})_{x∈𝕏} ∈ ℝ^{𝕏}. Then lim_{x∈𝕏} a_{x} exists and is equal to a if and only if there exist functions u, ℓ from the set of prime powers to the set of real numbers which converge to a such that ℓ(q_{x}) ≤ a_{x} ≤ u(q_{x}) for all x ∈ 𝕏. In this case, we also say that a_{x} is asymptotically equal to a for q ⟶ ∞.

Moreover, following the usual terminology in the analysis of algorithms, we suppress the set 𝕏 from the notation.

Overview and historical comments

We give an overview on the proof of the theorems.

The algorithms follow the index calculus strategy. Briefly, this means: First a so-called factor base is fixed. This is a finite set of prime divisors (closed points); in our case this is a subset F of C(𝔽_{q}). Now in a basic index calculus, one searches for relations between input elements, factor base elements and maybe some further elements of Cl^{0}(C). If enough relations have been obtained, one eliminates the factor base elements and tries to obtain a non-trivial relation between input elements. From this relation one then tries to derive the sought-after discrete logarithm.

For curves of a fixed genus ≥ 3, it has already been argued in [17] that by using a large prime variation, one can obtain a reduction in the expected running time which is superpolynomial in the input length. A further reduction can be obtained by using a double large prime variation; this has been studied in [6], [13] and [3].

In a double large prime variation, one fixes a set L of so called large primes; in our case this is C(𝔽_{q})−F. Then one searches for relations involving up to two large primes. Such relations are stored in a graph on the set of vertices L ˙∪ {∗}. Here a relation involving one large prime P is stored as a labeled edge between ∗ and P, and a relation involving two distinct large primes P and Q is stored as a labeled edge between P and Q. Later, this graph is then used to generate relations between input elements and factor base elements.

The result in [3] given at the beginning of this article is proven with the construction of a tree of large prime relations (an idea which goes back to [6]). Moreover, in order to control the depth of the tree, similarly to the algorithm in [13], the tree is constructed in stages.

The algorithms of this work also use a tree of large prime relations, which is again constructed in stages. The essential difference to the algorithm in [3] is that we construct the tree and also the factor base in a different way: We generate relations by intersecting the plane model with lines. Let D_{∞} := div(Z_{|C}). The crucial (but trivial) observation is that if D = ∑_{P ∈C} n_{P} P is a divisor in the linear system 𝔡, then D is linearly equivalent to D_{∞}, and we have a relation

∑_{P ∈C} n_{P} [P] = [D_{∞}] .  (2)

In [1] we gave an algorithm in which a graph of large prime relations is generated by intersecting the curve with lines running trough two points of the factor base. On a heuristic basis, we already argued that for any fixed d ≥ 4, one can with this algorithm solve the discrete logarithm problem in degree 0 class groups of curves given by plane models of degree d in an expected time of

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

Further evidence, including experimental data, that the result is valid for non-hyperelliptic curves of genus 3 (given by plane curves of degree 4) is given in [5]. However, even in this restricted case, no proof has been given until now.

In order to obtain the two theorems mentioned above, we modify the algorithm in [1] in some ways. As already mentioned, we employ a stagewise construction of a tree of large prime relations. In contrast, in [1] we first constructed a “full” graph of large prime relations. Moreover, during the construction of the tree, we also repeatedly enlarge the factor base (and shrink the set of large primes). The enlargements are done at the beginning of each stage in a randomized manner; we perform these enlargements to generate new randomness for each stage of the construction of the tree. To our knowledge, such enlargements of the factor base have not been suggested before.

The rest of this work is organized as follows: In the next section, we establish asymptotic results on the number of divisors in 𝔡 which split completely into distinct points. In particular, we prove Theorem 3. In the third section, we give the algorithm for Theorems 1, 2 and 4. In the first subsection of this section, we demonstrate that by our previous work [3], we only have to give a suitable algorithm for the construction of a tree of large prime relations. In the second subsection, we give such an algorithm. The final subsection of this section contains the analysis of this algorithm, based on combinatorial and probabilistic techniques.

2 Estimates on completely split divisors

The purpose of this subsection is to give asymptotic estimates on the number of completely split divisors in 𝔡 which split completely into distinct points. We establish two results. The first one is an asymptotic lower bound under the condition that there exists at least one such divisor (Proposition 3). The second result is Theorem 3.

We consider curves C/𝔽_{q} represented by plane models of degree a fixed degree d. For the moment, we do not make any assumption on the plane models.

All asymptotic statements in this section are on isomorphism classes of tuples consisting of a curve C/𝔽_{q}, a plane model C_{pm} of C of degree d a birational morphism C ⟶ C_{pm} and sometimes additionally a k-rational point on the curve.

Asymptotic lower bounds

Proposition 2 For P ∈ C(𝔽_{q}) such that there exists a divisor in 𝔡 containing P which splits completely into distinct points, the number of divisors in 𝔡 which split completely into distinct points and contain P is ≳ \frac{1}{(d−1)!} · q.

Proof. Let P be such a point. Let c : C ⟶ ℙ_{𝔽_{q}}^{1} be defined by the central projection with center P. (c is unique up to an automorphism of ℙ_{𝔽_{q}}^{1}.) Then c is a covering of degree ≤ d − 1. (The degree is d − 1 if and only if P does not lie over a singular point of C_{pm}.) Note that by adding π^{−1}(π(P)), we get a bijection between the pull-backs of the 𝔽_{q}-rational points of ℙ_{𝔽_{q}}^{1} to C and the divisors of 𝔡 containing P.

We denote points on curves and the corresponding places of function fields in the same way, and we now consider the extension of function fields 𝔽_{q}(C)|𝔽_{q}(ℙ^{1}) corresponding to c. Now c(P) is unramified and completely split in 𝔽_{q}(C). The fact that it is unramified implies that the extension is separable; let M be a Galois closure.

Recall that a place of degree 1 of 𝔽_{q}(ℙ^{1}) splits completely in 𝔽_{q}(C) if and only if it splits completely in M.

This implies that c(P) splits completely in M, and this implies that 𝔽_{q} is the exact constant field of M. Now with the effective Chebotaryov density theorem from [12], we conclude that the number of places of 𝔽_{q}(ℙ^{1}) of degree 1 which split completely in M (or in 𝔽_{q}(C)) is in \frac{1}{deg(c)!}q + O(q^{\frac{1}{2}} ).

This gives the proposition. □

Proposition 3 Suppose that there exists at least one divisor in 𝔡 which splits completely into distinct points. Then there are ≳ \frac{1}{d·(d−2)!·(d−1)!} · q^{2} such divisors.

Proof. Let P ∈ C(𝔽_{q}) be a point which is contained in a divisor which splits completely into distinct points. By the previous proposition, we have ≳ \frac{1}{(d−1)!} ·q divisors which split completely into distinct points and contain P. Altogether, these divisors contain ≳ \frac{d−1}{(d−1)!} · q^{2} = \frac{1}{(d−2)!} · q^{2} points of C(𝔽_{q}). Now for each point in such a divisor, we apply the previous proposition again. We obtain in this way ≳ \frac{1}{(d−2)!·(d−1)!} · q^{2} distinct tuples (Q, D) ∈ C(𝔽_{q}) × 𝔡, where D splits completely into distinct points and contains Q. This gives ≳ \frac{1}{d·(d−2)!·(d−1)!} ·q^{2} divisors in 𝔡 which split completely into distinct points.□

Proof of Theorem 3

For d = 3, Theorem 3 is immediate. Indeed, in this case, every line through two distinct points of C_{ns}(𝔽_{q}) gives rise to a completely split divisor. (We included this case only for completeness.)

Let us now assume that d ≥ 4. We first explain the general strategy for the proof.

For each point P ∈ C_{ns}(𝔽_{q}) we wish to estimate the number of divisors in 𝔡 which split completely into distinct points and contain P. For this, we proceed similarly to the proof of Proposition 2.

We consider a covering c : C ⟶ ℙ_{𝔽_{q}}^{1} defined by the central projection with center P. This is a covering of degree d − 1, and by adding P, we get a bijection between the pull-backs of the 𝔽_{q}-rational points of ℙ_{𝔽_{q}}^{1} to C and the divisors of 𝔡 containing P. We are therefore interested in the number of 𝔽_{q}-rational points Q of ℙ_{𝔽_{q}}^{1} which are unramified under the covering c such that c^{−1}(Q) splits into distinct 𝔽_{q}-rational points of C where none of these points is equal to P.

As above, we consider the extension of function fields 𝔽_{q}(C)|𝔽_{q}(ℙ^{1}) corresponding to c. A first necessary condition in order that there is any 𝔽_{q}-rational point Q of ℙ_{𝔽_{q}}^{1} such that c^{−1}(Q) splits completely into distinct distinct 𝔽_{q}-rational points is that the extension of function fields is separable. This condition is satisfied if and only if there are only finitely many closed points of ℙ_{𝔽_{q}}^{1} which are ramified with respect to c.

Let us now assume that the extension is indeed separable. Let M be a Galois closure of the extension. Recall again that a place of 𝔽_{q}(ℙ^{1}) splits completely in 𝔽_{q}(C) if and only if it splits completely in M.

As already mentioned above, a second necessary condition in order that there is any place of degree 1 of 𝔽_{q}(ℙ^{1}) which splits completely in M is that 𝔽_{q} is the exact constant field of M. On the other hand, if this condition is satisfied, by the effective Chebotaryov density theorem from [12], the number of such places is in \frac{1}{(d−1)!} · q + O(q^{\frac{1}{2}} ).

The condition that 𝔽_{q} is the exact constant field of M is satisfied if and only if [M : 𝔽_{q}(ℙ^{1})] = [\overline{𝔽}_{q}M : \overline{𝔽}_{q}(ℙ^{1})], and this is in particular satisfied if [\overline{𝔽}_{q}M : \overline{𝔽}_{q}(ℙ^{1})] = (d − 1)!, that is, Gal(\overline{𝔽}_{q}M|\overline{𝔽}_{q}(ℙ^{1})) ≈ S_{d−1}.

Now the argument is different according to whether d = 4 or d > 4 and the plane model is assumed to be reflexive.

d = 4

This case was already considered in [5]. Note first that as the degree of a covering c as above is prime and the genus of C is ≥ 1 by assumption, the extension of function fields is indeed separable (see [7, Proposition 2.5]).

The essential observation is now: If c_{\overline{𝔽}_{q}} : C_{\overline{𝔽}_{q}} ⟶ ℙ_{\overline{𝔽}_{q}}^{1} does not have a non-trivial automorphism, then the corresponding extension of function fields \overline{𝔽}_{q}(C)|\overline{𝔽}_{q}(ℙ^{1}) is not Galois, and therefore Gal(\overline{𝔽}_{q}M|\overline{𝔽}_{q}(ℙ^{1})) ≈ S_{3}.

We therefore obtain:

Proposition 4 For P ∈ C(𝔽_{q}) such that the corresponding covering C_{\overline{𝔽}_{q}} ⟶ ℙ_{\overline{𝔽}_{q}}^{1} over \overline{𝔽}_{q} does not have a non-trivial automorphism, the number of divisors in 𝔡 which split completely into distinct points is in

\frac{1}{6} · q + O(q^{\frac{1}{2}} ) .

As we assumed that genus of C be ≥ 1, the number of automorphisms of degree 3 of C is in O(1). So the number of points of C(𝔽_{q}) for which the assumption does not hold is in O(1). The proposition then easily implies Theorem 3 under the assumption that d = 4.

C_{pm} reflexive

We use the following general result:

Proposition 5 Let L|K be a finite separable extension of fields of degree n such that L|K does not contain an intermediate field distinct from K and L and there is a non-archimedean place Q of K with discrete valuation which splits in L in the form 2P_{1} + P_{2} + P_{3} + ⋯ + P_{n−1} for distinct places P_{i} of L.^{1} Then the Galois group of a Galois closure of L|K is isomorphic to S_{n}.

Proof. Let M be a Galois closure of the extension. Then Gal(M|K) acts on the set of embeddings of L into M; we consider Gal(M|K) as a permutation group on this set. This operation is of course transitive. Moreover, the condition that L|K does not contain a proper subfield is equivalent to the permutation group being primitive.

Let R be a place of M lying over P, G_{R|P} the decomposition group and Z_{R} the decomposition field. Let L be generated over K be the root of an irreducible polynomial f(X) ∈ K[X]. It follows from [14, Satz 8.2] and [14, Satz 9.8] that f(X) splits over Z_{R} as

f(X) = f_{1}(X)(X − α_{2}) ⋯ (X − α_{n−1}) ,

where f_{1}(X) is irreducible and quadratic and the α_{i} ∈ K are pairwise distinct. The group G_{R|P} is therefore cyclic of order 2, and it fixes the α_{i} and permutes the two roots of f_{1}(X) in M.

Now the non-trivial automorphism in G_{R|P} acts as a transposition. We therefore have a transitive primitive permutation group with a transposition. With [20, Theorem 13.3] we conclude that the group is the full symmetric group. □

From this general proposition the following result follows immediately:

Proposition 6 Let \overline{k} be an algebraically closed field, and let L|\overline{k}(x) be a finite extension of degree n ≥ 3. Suppose that there are only finitely many places of \overline{k}(x) over \overline{k} which are ramified in L and that every such place splits in L as 2P_{1} + P_{2} + P_{3} + ⋯ + P_{n−1} for distinct places P_{i}. Then the extension L|\overline{k}(x) is separable and its monodromy group is isomorphic to S_{n}.

Proof. Under the given conditions the extension is obviously separable. Moreover, it cannot contain an intermediate field different from L and \overline{k}(x). For, let N be an intermediate field distinct from \overline{k}(x). As every finite extension of \overline{k}(x) is ramified, there exists a place Q of the function field \overline{k}(x) which is ramified in N. Let us fix such a place, let R be a ramified place of N|\overline{k}(x) over Q, and let r be the ramification degree. Furthermore, let a := [L : N]. Then the conorm of Q in L has the form rD + D̃ for effective divisors D, D̃ of the function field L with deg(D) = a (and r ≥ 2). By our assumption it follows that a = 1 (and r = 2).

Now the statement follows with the previous proposition. □

1The additive notation is of course unusual in this general setting. We use it here for consistency.

We now make use of the classical theory of plane curves (geometrically irreducible and geometrically reduced 1-dimensional varieties in the projective plane in our terminology), including duality theory. A good reference for this classical theory in characteristic 0 is [18], the key statements we need for reflexive curves in positive characteristic can be found in [8].

For a closed point P of C_{\overline{𝔽}_{q}}, the multiplicity of the divisor π^{−1}(π(P)) at P is called the order of P (with respect to fixed plane model C_{pm} and the map π).

Now for each closed point P of C_{\overline{𝔽}_{q}} (including points lying over singular points of (C_{pm})_{\overline{𝔽}_{q}}) there is exactly one line L in ℙ_{\overline{𝔽}_{q}}^{2} such that the multiplicity of the divisor π^{−1}(L) at P is larger than the order of P. Following [18, IV, 5.3], we call this line the tangent at P. In [18] the tangent at P is characterized as the tangent to the local branch of (C_{pm})_{\overline{𝔽}_{q}} corresponding to P. There is the following alternative proof of existence and uniqueness of the tangent without power series which is important for our applications: We consider a covering c : C_{\overline{𝔽}_{q}} ⟶ ℙ_{\overline{𝔽}_{q}}^{1} defined by central projection with center π(P). There exists exactly one closed point Q of ℙ_{\overline{𝔽}_{q}}^{1} whose pull-back to C_{\overline{𝔽}_{q}} contains P. Now exactly for this point Q, the multiplicity of P in the divisor π^{−1}(π(P)) + c^{−1}(Q) ∈ 𝔡 is larger than the order of P. The line which defines this divisor is the tangent at P.

If L is the tangent at P, the multiplicity of π^{−1}(L) at P is called the class of P; cf. [18]. If π(P) is non-singular, P is called a flex point if and only if the class of P is greater than 2.

Let τ : C ⟶ C_{pm}^{∗} be the canonical map from C to the dual model associated to C_{pm} and π. This means that for every closed point P of C_{\overline{𝔽}_{q}}, τ(P) is the point corresponding to the tangent at P.

A tangent is called ordinary if it is the tangent of exactly one closed point of C_{\overline{𝔽}_{q}} and the intersection multiplicity at this point is 2 (that is, the class of the point is 2).

Lemma 7 Let P be a closed point of (C_{ns})_{\overline{𝔽}_{q}}. Then the tangent at P is ordinary if and only if the point τ(P) is a non-singular point of the dual model (C_{pm}^{∗})_{\overline{𝔽}_{q}}.

Proof. It is obvious that more than one point of C_{\overline{𝔽}_{q}} lies over τ(P) if and only if the tangent at P is also the tangent of another point of C_{\overline{𝔽}_{q}}.

We claim that P is a flex point of (C_{pm})_{\overline{𝔽}_{q}} if and only if the order of P with respect to (C_{pm}^{∗})_{\overline{𝔽}_{q}} and τ is greater than 1.

Let s be the class of P. As P is non-singular, there exist homogeneous coordinates such that with respect to this coordinate system P is given by [0 : 0 : 1] and a reduced parametrization

[t : b_{s}t^{s} + b_{s+1}t^{s+1} + b_{s+2}t^{s+2} + ⋯: 1] ,

where b_{s} ≠ 0. Now the image of this \overline{𝔽}_{q}((t))-valued point in the dual curve is given by the vector product of the parametrization and its derivative; this is

[b_{s}st^{s−1} + ⋯: −1 : b_{s}(1 − s)t^{s} + ⋯] .

(The corresponding result in characteristic 0 is a classical result from duality theory of curves. By [8, Remark 2.6] the result also holds in positive characteristic.)

As the map τ : C_{pm} ⟶ C_{pm}^{∗} is birational, it induces an isomorphism of function fields, so we again have a reduced parametrization.

Let p be the characteristic of the ground field. Then the order of P with respect to C_{pm}^{∗} and τ is s − 1 except if p|s in which case the order is ≥ s. As p > 2, we conclude: P is a flex point if and only if its order with respect to C_{pm}^{∗} and τ is > 1. □

Lemma 8 The number of non-ordinary tangents of C_{\overline{𝔽}_{q}} is in O(1).

Proof. The number of closed points of C_{\overline{𝔽}_{q}} which lie over a singular point of (C_{pm})_{\overline{𝔽}_{q}} is < \frac{(d−1)(d−2)}{2}. So the number of tangents running through these points is also bounded by this number.

By the previous lemma, we now have to bound the number of points lying over singular points of the dual model. It is a classical result that the degree of the dual model C_{pm}^{∗} is bounded by d · (d − 1). (Briefly, the argument is as follows: The degree of C_{pm}^{∗} is given by the number of intersection points of (C_{pm}^{∗})_{\overline{𝔽}_{q}} with a line in the dual plane which does not run through the singularities of (C_{pm}^{∗})_{\overline{𝔽}_{q}}. Such a line corresponds to a point P ∈ ℙ^{2}(\overline{𝔽}_{q}), and the intersection points of the line with (C_{pm}^{∗})_{\overline{𝔽}_{q}} correspond to the tangents of C_{\overline{𝔽}_{q}} passing through P (which are all ordinary). The corresponding points on (C_{pm})_{\overline{𝔽}_{q}} are contained in the intersection of (C_{pm})_{\overline{𝔽}_{q}} with the polar curve for (C_{pm})_{\overline{𝔽}_{q}} and P, which has degree d − 1. The result now follows with Bezout’s theorem.)

This implies that the arithmetic genus of C_{pm}^{∗} is bounded by \frac{1}{2} · (d − 3) · (d − 2)^{2} · (d − 1), and in particular the number of closed points of C_{\overline{𝔽}_{q}} lying over singular points of (C_{pm}^{∗})_{\overline{𝔽}_{q}} is bounded by this number. □

The previous lemma implies immediately:

Lemma 9 The number of closed points P of C_{\overline{𝔽}_{q}} such that some non-ordinary tangent passes through P is in O(1). (We consider all tangents of all closed points of C_{\overline{𝔽}_{q}} which pass through P, not only the unique tangent at P.)

Proposition 10 For P ∈ C_{ns}(𝔽_{q}) such that only ordinary tangents pass through P, the number of divisors of 𝔡 which contain P and split completely into distinct points is in

\frac{1}{(d − 1)!} · q + O(q^{\frac{1}{2}} ) .

Proof. We consider a covering c_{\overline{𝔽}_{q}} : C_{\overline{𝔽}_{q}} ⟶ ℙ_{\overline{𝔽}_{q}}^{1} defined by P. By assumption, for every closed point Q of ℙ_{\overline{𝔽}_{q}}^{1}, the divisor c^{−1}(Q)+P ∈ 𝔡 either splits into distinct points or is of the form 2P_{1}+P_{2}+⋯+P_{d−1} for distinct points P_{i}. Moreover, the second case only happens for finitely many points (see proof of Lemma 8). Therefore, there are only finitely many ramified closed points of ℙ_{\overline{𝔽}_{q}}^{1}, and for every such point Q, we have c^{−1}(Q) = 2P̃_{1} + P̃_{2} + ⋯ + P̃_{d−2}

for distinct points P̃_{i}. By Proposition 6 and the general remarks at the beginning of the proof, the result follows. □

This proposition and Lemma 9 easily imply the statement in Theorem 3 under the assumption the plane model is reflexive.

3 The algorithm

3.1 General considerations

As indicated above, in the algorithm we construct a tree of large prime relations. Let us formally define what we mean by such a tree.

Let C be a curve over a finite field 𝔽_{q}. Let F be a set of prime divisors of C, and let L be another set of prime divisors of C which is disjoint from F. We call F the factor base and L the set of large primes. Furthermore, let some elements c_{1}, …, c_{u} ∈ Cl^{0}(C) be given.

Now a tree of large prime relations for the given data is an undirected labeled rooted tree whose vertices are contained in L ˙∪ {∗} with root ∗, where the edges are labeled as follows:

Each label is a tuple ((r_{F})_{F ∈F}, (s_{j})_{j=1,...,r}), where either each entry is an integer or each entry is a residue class modulo the group order which defines in the following way a relation:

• If the edge connects ∗ and a prime divisor P, the equality ∑_{F ∈F} r_{F} [F]+ [P] = ∑_{j} s_{j}c_{j} holds.

• If the edge connects two distinct prime divisors P and Q, the equality ∑_{F ∈F} r_{F} F + [P] + [Q] = ∑_{j} s_{j}c_{j} holds.

We only consider trees where the relations are given modulo the group order, and we store the labels in sparse representation. Furthermore, as already mentioned, we represent divisors and divisor classes as described in [3, Section 2].

If T is such a tree, we denote its set of vertices by V (T ). Now, by following the arguments in [3, Section 3], one can obtain:

Proposition 11 Let g and c ∈ ℕ with g, c ≥ 2 be fixed. Then there is an algorithm such that the following holds:

Under the input of

• a curve C of genus g, given by a plane model of bounded degree,

• the group order of Cl^{0}(C),

• two elements a, b ∈ Cl^{0}(C) with b ∈ ⟨a⟩,

• elements c_{1}, …, c_{u} ∈ Cl(C) whose degrees are bounded, where u is polynomially bounded in log(q),

• a factor base F ⊆ C(𝔽_{q}) of size Õ(q^{1− \frac{1}{c}}),

• a tree of large prime relations T for factor base F, set of large primes C(𝔽_{q}) − F and classes c_{1}, …, c_{u}

– of a depth which is polynomially bounded in log(q)

– with #(F ∪ V (T )) ≥ q^{1− \frac{1}{g} + \frac{1}{cg}}

– such that the number of non-trivial residue classes involved in each label is polynomially bounded in log(q),

the algorithm computes the discrete logarithm of b with respect to a in an expected time of

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

The algorithm thereby has storage requirements of Õ(#(F ∪ V (T )) · log(q)).

Our application

In order to obtain Theorems 1 and 2 (and therefore also Theorem 4), we are going to apply this proposition with c = d − 2. Here as throughout this article, d is the degree of the plane model under consideration. In our application, d is fixed, but the genus, g, is not. As for fixed degree there are only finitely many possibilities for the genus, there still exists an algorithm with the specified properties.

On the proof of the proposition. In [3] the statement in the proposition is proven for c = g, but the general case is no more difficult than the statement in [3]. We briefly recall the algorithm and its analysis, for details we refer to [3, Section 3]. For simplicity, we focus on the case the group order N is prime and generated by a.

Let P_{0} ∈ C(𝔽_{q}) be the point which is used to represent divisor classes, that is, a divisor class c on C is represented by the unique along P_{0} reduced divisor and the degree of c.

We repeatedly select uniformly randomly chosen elements α, β ∈ ℤ/Nℤ and compute the unique along P_{0} reduced divisor D with

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

in free representation. If D splits over the factor base and the vertices of the tree, we use the tree to obtain a “full relation”, that is, a relation between factor base elements, c_{1}, …, c_{u} and a, b. We stop this procedure if we have obtained #F +u+1 full relations. After that we try to compute the discrete logarithm via linear algebra. If this fails, we repeat the whole procedure.

Using an algorithm from sparse linear algebra, the linear algebra computation can be performed in an expected time of Õ(q^{2− \frac{2}{c}}). We have to show that the relation generation can also be performed in an expected time of Õ(q^{2− \frac{2}{c}}).

There exists a constant C > 0 such that the number of elements of Cl^{0}(C) which are represented by an along P_{0} reduced divisor which splits completely into factor base elements and vertices of the tree is at least

\frac{1}{g!} · q^{(1− \frac{1}{g} + \frac{1}{cg})·g} − C · q^{g−1} .

For q large enough, this is ≥ \frac{1}{2g!} · q^{(1− \frac{1}{g} + \frac{1}{cg})·g} = \frac{1}{2g!} · q^{g−1+ \frac{1}{c}}. Now for q large enough the probability that a uniformly randomly chosen group element is represented by a divisor which splits over the factor base and the vertices of the tree is at least

\frac{1}{4g!} · q^{(g−1+ \frac{1}{c})−g} = \frac{1}{4g!} · q^{−(1− \frac{1}{c})} .

The expected number of tries until we have one relation is therefore at most 4g!·q^{1− \frac{1}{c}}. Consequently, the expected number of tries until we have #F + u + 1 relations is in O(q^{2− \frac{2}{c}}), and the expected time is in Õ(q^{2− \frac{2}{c}}).

In the general case, we first construct a “potential generating system” c′_{1}, …, c′_{u′}. (In [3], c_{1}, …, c_{u} is already such a system, and we have u = u′ and c_{j} = c′_{j} for all j.) Then we try to generate relations between the factor base, a, b, c_{1}, …, c_{u} and c_{1}, …, c′_{u′} as follows: We choose s_{1}, …, s_{u′} uniformly randomly in ℤ/Nℤ, we 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. Again, if D splits over the factor base and the vertices of the tree, we use the tree to obtain a “full relation”, which is now a relation between the factor base elements, the classes c_{1}, …, c_{u}, c_{1}, …, c′_{u′} and a, b.

As above, if we have enough relations, we try to solve for the discrete logarithm. Moreover, we stop and restart the whole algorithm if a predefined time bound has been reached. □

3.2 Construction of the tree of large prime relations

The discrete logarithm problem in elliptic curves can be solved in a time of Õ(q^{\frac{1}{2}} ). Moreover, by Theorem 3, for d = 4 and q large enough the linear system 𝔡 as defined above contains a divisor which splits completely into distinct points. We thus consider curves of genus ≥ 2 represented by plane models of a fixed degree d ≥ 4 such that the linear system 𝔡 contains a divisor which splits completely into distinct points. As already mentioned, we want to apply Proposition 11 with c = d − 2 in order to prove Theorems 1 and 2.

The L-polynomial of a curve as specified, and therefore also the group order, can be computed in polynomial time via Pila’s extension of Schoof’s algorithm ([15], [16]).

Our goal is now to give an algorithm with the following properties:

1. Under an input as specified, the algorithm outputs a factor base and a tree of large prime relations satisfying the assumptions of Proposition 11 with c = d − 2, u = 1 and c_{1} = [D_{∞}], D_{∞} = div(Z_{C}).

2. The expected running time of the algorithm is in Õ(q^{2− \frac{2}{d−2}} ).

We now outline such an algorithm and begin with the analysis of the algorithm. The analysis is completed in the next subsection. This analysis then also completes the proof of Theorems 1 and 2.

Let us first discuss some basic computations.

Lemma 12 One can compute a uniformly randomly distributed point in C(𝔽_{q}) in an expected time which is polynomially bounded in log(q).

This is Proposition 3.8 in [3].

Lemma 13 Given a linear form W ∈ 𝔽_{q}[X, Y, Z]_{1}, one can compute the divisor div(W_{|C}) ∈ 𝔡 in free representation in an expected time which is polynomially bounded in log(q).

Sketch of a proof. We choose some linear form U such that the intersection between the two lines defined by W and U does not lie on C_{pm}. Then we have div(W_{|C}) = (\frac{W_{|C}}{U_{|C}})_{+}, the positive part of the principal divisor (\frac{W_{|C}}{U_{|C}}). With these considerations, the computation can be performed with standard algorithms on ideal arithmetic. □

Remark 14 In fact, we only need an algorithm to determine if a line runs through C_{ns}, defines a completely split divisor, and in this case to compute such a divisor. This task can easily be achieved by inserting the equation for the line into the curve equation, factoring the resulting polynomial and finally by checking for each root if all partial derivatives vanish.

Construction of the tree

For the construction of the tree, we use a “stage-wise procedure” which is based on successive enlargements of the factor base. As in the previous subsection, we denote the tree by T and its set of vertices by V (T ). The factor base is always denoted by F.

The following algorithm has the desired expected running time. However, it is conceivable that this algorithm violates the desired storage requirements of Õ(q^{1− \frac{1}{g} + \frac{1}{(d−2)g}}) for g ≥ d − 1. At the end of this section we point out modifications leading to an algorithm which also has the desired storage requirements.

Let a curve C/𝔽_{q}, represented by a plane model C_{pm} of degree d, be given. A first step is the computation of the genus g. This can be achieved in

polynomial time with the algorithms in [10] (see also [3]). We then construct the factor base and the tree with the following stages:

Stage 0

We determine a subset F_{0} of C_{ns}(𝔽_{q}) of size ⌈log(q) · q^{1− \frac{1}{d−2}} ⌉ such that through each point of F_{0} there passes at least one line which splits completely into distinct points of C(𝔽_{q}). For this, we repeatedly choose lines uniformly at random and compute the corresponding divisor. Note that the probability that a line gives rise to a divisor which splits completely into distinct points is in Ω(1) by Proposition 3, thus the expected running time is in Õ(q^{1− \frac{1}{d−2}} ).

Stage 1

We choose a subset F_{1} of C_{ns}(𝔽_{q}) − F_{0} of size ⌈(5 · (d − 1)!^{2})^{\frac{1}{d−2}} · q^{1− \frac{1}{d−2}} ⌉ uniformly randomly from the set of all such subsets; the constant (5 · (d − 1)!^{2})^{\frac{1}{d−2}} will be justified in retrospect in the analysis of the algorithm. By Lemma 12 this task can also be achieved in an expected time of Õ(q^{1− \frac{1}{d−2}} ).

We iterate over all lines passing through two distinct points of F_{1}. For each such line, we compute the corresponding divisor D on C in free representation.

Now for every such divisor D, we check if it splits in the form

D = P_{1} + ⋯ + P_{d−1} + Q  (3)

with P_{i} ∈ F_{0} ∪ F_{1} and Q ∈ C_{ns}(𝔽_{q}) − (F_{0} ∪ F_{1}). If this is the case, we store the divisor.

After the consideration of all lines we choose for each point Q as in (3) one divisor as above. If then we have ≥ ⌈q^{1− \frac{1}{d−2}} ⌉ distinct points Q (and corresponding divisors), we set the factor base as F := F_{0} ∪F_{1}, and for each such divisor, we insert an edge from ∗ to Q with the data for the relation

[P_{1}] + ⋯ + [P_{d−1}] + [Q] = [D_{∞}]

into the tree.

If we do not have enough points, we choose another subset F_{1} and repeat.

Stages ≥ 2.

At the beginning of Stage s ≥ 2, we have a factor base F ⊆ C_{ns}(𝔽_{q}) and a tree T . We now choose a set G ⊆ C_{ns}(𝔽_{q}) − (F ∪ (V (T ))) of size ⌈(5 · (d − 1)!^{2})^{\frac{1}{d−2}} · q^{1− \frac{1}{d−2}} ⌉ uniformly randomly from the set of all such subsets. We then consider all lines through two distinct points of G. For each such line, we check if it defines a divisor D of the form

D = P_{1} + ⋯ + P_{d−2} + P + Q  (4)

with P_{i} ∈ G for i = 1, …, d − 2, P ∈ F ∪ V (T ) and Q ∈ C(𝔽_{q}) − (F ∪ G ∪ V (T )).

After the consideration of all lines we choose for each point Q as in (4) one divisor as above. If then we have ≥ ⌈2^{s} · q^{1− \frac{1}{d−2}} ⌉ distinct points Q (and corresponding divisors), we update F as F ∪ G, and for each such divisor, we insert an edge from P to Q with a label for the relation

[P_{1}] + ⋯ + [P_{d−2}] + [P] + [Q] = [D_{∞}]

into the tree.

Otherwise, we restart the computation of Stage s with another set G.

The end

We stop the computation after s^{final} := ⌈log_{2}(q) · (\frac{1}{d−2} − \frac{1}{g} + \frac{1}{(d−2)g})⌉ stages.

Note that then the tree has ≥ q^{1− \frac{1}{g} + \frac{1}{(d−2)g}} leaves.

What one has to prove

Clearly, the number of stages is in O(log(q)) (and thus so is the depth of the tree), and the size of the factor base is in O(q^{1− \frac{1}{d−2}} ). Moreover, by the lemmata above, the computation of each stage can be performed in an expected time of Õ(q^{2− \frac{2}{d−2}} ).

Let us call an abstract state a tuple consisting of a curve C/𝔽_{q}, a plane model C_{pm} of C of degree d, a birational morphism π : C ⟶ C_{pm}, a factor base F ⊆ C_{pm}(𝔽_{q}) and a tree of large prime relations T with relations as described in the algorithm above.

Now, for any s with 1 ≤ s ≤ s^{final} and any abstract state S of any computation at the beginning of Stage s, let p_{S,s} be the conditional probability that the computation of Stage s is successful after one repetition. Note that if the computation is not successful after one repetition then the abstract state at the beginning of the next repetition is again S. Thus the expected number of repetitions of Stage s under the condition that Stage s is entered with state S is \frac{1}{p_{S,s}}.

So, all we have to prove to obtain Theorems 1 and 2 is:

Proposition 15 There exists a constant κ > 0 such that for q large enough, for all s with 1 ≤ s ≤ s^{final} and all abstract states S of the computation at the beginning of Stage s, p_{S,s} ≥ κ.

The goal of the next subsection is to prove this proposition. The proof is based on the results of the previous section and on combinatorial and probabilistic arguments. The main result of the next section is Proposition 18; a proof of Proposition 15 then follows by suitable applications of Proposition 18. This final argument is at the end of the next subsection.

It follows a more formal description of the algorithm for the construction of the factor base and the tree of large prime relations.

Algorithm: Construction of the factor base and the tree of large prime relations

Input: A curve C/𝔽_{q}, represented by a plane model C_{pm} of the fixed degree d.

Output: A factor base and a tree of large prime relations satisfying the requirements of Proposition 11 for c = d − 2.

Compute the genus g of the curve. Construct a set F ⊆ C(𝔽_{q}) and a labeled rooted tree T with vertex set contained in C(𝔽_{q}) ˙∪ {∗} as follows:

Let T consist only of the root ∗. Determine a subset F_{0} of C_{ns}(𝔽_{q}) of size ⌈log(q) · q^{1− \frac{1}{d−2}} ⌉ as follows: Repeat

Choose a linear form W ∈ 𝔽_{q}[X, Y, Z]_{1} uniformly at random and compute the divisor D := div(W_{|C}). If D splits completely into distinct points of C_{ns}(𝔽_{q}), insert one of these points in C_{ns}(𝔽_{q}) into F_{0}.

Until F_{0} has size ⌈log(q) · q^{1− \frac{1}{d−2}} ⌉.

Repeat Choose F_{1} ⊆ C_{ns}(𝔽_{q}) of size ⌈(5·(d−1)!^{2})^{\frac{1}{d−2}} ·q^{1− \frac{1}{d−2}} ⌉ uniformly randomly from the set of all such subsets. Construct a list L of divisors in free representation as follows: Iterate over all lines passing through two distinct points of F_{1}. Whenever such a line defines a divisor of the form

P_{1} + ⋯ + P_{d−1} + Q

with P_{i} ∈ F_{0} ∪ F_{1} and Q ∈ C_{ns}(𝔽_{q}) − (F_{0} ∪ F_{1}), store the divisor in L. Sort L for the points Q ∈ C_{ns}(𝔽_{q}) − (F_{0} ∪ F_{1}) occurring in the divisors, for each such point choose one divisor and delete the others.

Until L contains ≥ q^{1− \frac{1}{d−2}} divisors. Let F ⟵ F_{0} ∪ F_{1}. For each divisor in L, insert an edge from ∗ to Q into T , labeled with the data for the corresponding relation.

For s = 2, …, ⌈log_{2}(q) · (\frac{1}{d−2} − \frac{1}{g} + \frac{1}{(d−2)g})⌉ do

Repeat Choose G ⊆ C_{ns}(𝔽_{q})−V (T ) of size ⌈(5·(d−1)!^{2})^{\frac{1}{d−2}} ·q^{1− \frac{1}{d−2}} ⌉ uniformly randomly from the set of all such subsets. Construct a list L of divisors in free representation as follows: Iterate over all lines passing through two distinct points of G. Whenever such a line defines a divisor of the form

P_{1} + ⋯ + P_{d−2} + P + Q

with P_{i} ∈ G, P ∈ F ∪ V (T ) and Q ∈ C_{ns}(𝔽_{q}) − (F ∪ G ∪ V (T )), store the divisor in L.

Sort L for the points Q ∈ C_{ns}(𝔽_{q}) − (F ∪ G) occurring in the divisors, for each such point choose one divisor and delete the others.

Until L contains ≥ 2^{s} · q^{1− \frac{1}{d−2}} divisors.

Let F ⟵ F ∪ G.

For each divisor in L, insert an edge from P to Q into T , labeled with the data for the corresponding relation.

Output F, T

On the storage requirements

We wish to have an algorithm with storage requirements of Õ(max(q^{1− \frac{1}{d−2}} , q^{1− \frac{1}{g} + \frac{1}{(d−2)g}})) (which is Õ(q^{1− \frac{1}{g} + \frac{1}{(d−2)g}}) for g ≥ d − 3). It is however conceivable that the size of the lists in the algorithm above does not satisfy the desired bound. The bound can be guaranteed with the following minor modification of each stage of the algorithm:

One maintains a sorted list L already during the construction (via a balanced binary search tree), where the sorting is for the points Q in the divisors, where Q is as in the algorithm. One always inserts at most one relation for each point of C(𝔽_{q})−(F_{0} ∪F_{1}) (for Stage 1) respectively C(𝔽_{q})− (F ∪ V (T )) (for Stage s > 1) into the list. Moreover, one stops the construction if #F +#V (T )+#L ≥ q^{1− \frac{1}{g} + \frac{1}{(d−2)·g}}. One then inserts all the new points into the tree and stops the whole computation.

Otherwise the algorithm is not changed.

3.3 Analysis of the construction of the tree

We now analyze the construction of the tree. Let for this d ≥ 4 still be fixed.

Proposition 16 We consider a set of isomorphism classes of tuples consisting of: a curve C/𝔽_{q}, a plane model C_{pm} of degree d of C, a birational morphism π : C ⟶ C_{pm} and a subset S ⊆ C_{ns}(𝔽_{q}) with #S ∈ o(q) such that for every point P ∈ S there exists a divisor in 𝔡 which splits completely into distinct points and contains P.

Then there are ≳ \frac{1}{2(d−1)!} · q points Q ∈ C_{ns}(𝔽_{q}) − S such that there is are at least \frac{1}{2(d−1)!} · #S divisors in 𝔡 which split completely into distinct points of C_{ns}(𝔽_{q}) and contain Q and exactly one point from S.

Proof. By Proposition 2, for q large enough, the following holds: For P ∈ S the number of divisors in 𝔡 which split completely into distinct points of C_{ns}(𝔽_{q}) and contain P is ≳ \frac{1}{(d−1)!} · #C_{ns}(𝔽_{q}).

As the divisors in 𝔡 are defined by lines, for every P ∈ S, the number of divisors as above which also contain another point from S is < #S ∈ o(q). Thus for P ∈ S, the number of such divisors which do not contain another point from S is again ≳ \frac{1}{(d−1)!} · #C_{ns}(𝔽_{q}). Altogether, we have ≳ \frac{1}{(d−1)!} · #C_{ns}(𝔽_{q}) · #S divisors in 𝔡 which split completely into distinct points and contain exactly one point from S.

Every point outside of S is contained in at most #S such divisors. Let c be the fraction of points of C_{ns}(𝔽_{q}) which contain ≥ \frac{1}{2(d−1)!} ·#S such divisors. Then altogether we have < (c · #S + (1 − c) · \frac{1}{2(d−1)!} · #S) · #C_{ns}(𝔽_{q}) = (\frac{1}{2(d−1)!} + (1 − \frac{1}{2(d−1)!}) · c) · #S · #C_{ns}(𝔽_{q}) such divisors. This implies that

\frac{1}{(d − 1)!} ≲ \frac{1}{2(d − 1)!} + (1 − \frac{1}{2(d − 1)!}) · c ,

which implies

c ≳ \frac{\frac{1}{2(d−1)!}}{1 − \frac{1}{2(d−1)!}} = \frac{1}{2(d − 1)! − 1} > \frac{1}{2(d − 1)!} ·

□

Proposition 17 Let c > 0 be fixed. We consider a set of isomorphism classes of tuples consisting of

• a curve C/𝔽_{q}, a plane model C_{pm} of degree d of C and a birational morphism π : C ⟶ C_{pm},

• a subset S ⊆ C_{ns}(𝔽_{q}) with q^{\frac{1}{d−2}} ∈ O(#S) and #S ∈ o(q) such that for every point P ∈ S there exists a divisor in 𝔡 which splits completely into distinct points and contains P,

• Q ∈ C_{ns}(𝔽_{q}) − S such that there are at least \frac{1}{2(d−1)!} · #S divisors in 𝔡 which split completely into distinct points of C_{ns}(𝔽_{q}) and contain exactly one point from S and Q.

For such a tuple, we set u := ⌈c · q^{1− \frac{1}{d−2}} ⌉.

Then the following holds: For a random subset^{2} U of C_{ns}(𝔽_{q}) − S which is uniformly randomly distributed among all subsets of cardinality u, the probability that there is a divisor in 𝔡 which

- splits completely into distinct points of C_{ns}(𝔽_{q}),

- contains Q, exactly one point of S and otherwise only points of U is

2By a random subset of a set A we mean a random variable with values in the power set of A.

≳ \frac{c^{d−2}}{2(d − 1)!} · \frac{#S}{q} ·

(We do not impose a condition on Q not being in U.)

For later use, we will prove a more accurate result with an error term (see Equation (8)). Proof. For some divisor D ∈ 𝔡 which splits completely into distinct points of C_{ns}(𝔽_{q}) and contains Q and exactly one point from S let p_{D} be the probability that all points of D distinct from Q as well as the point in S lie in U.

Similarly, let for two distinct divisors D_{1}, D_{2} ∈ 𝔡, each splitting completely into distinct points of C_{ns}(𝔽_{q}) and containing Q and exactly one point from S p_{D_{1},D_{2}} be the probability that all points of D_{1} and D_{2} distinct from Q as well as the points in S lie in U.

Let p be the probability we wish to estimate in the proposition. We have

p ≥ ∑_{D} p_{D} − \frac{1}{2} ∑_{D_{1},D_{2}} p_{D_{1},D_{2}} ,

where the sums range over all divisors specified above. Now

p_{D} = \begin{matrix}( & {#C_{ns}(𝔽_{q})−#S−(d−2) \atop u−(d−2)} & ) \\ ( & {#C_{ns}(𝔽_{q})−#S \atop u} & ) \end{matrix}

= \frac{(u − d + 3) · (u − d + 4) ⋯ u}{(#C_{ns}(𝔽_{q}) − #S − d + 3) ⋯ (#C_{ns}(𝔽_{q}) − #S)} ,

p_{D_{1},D_{2}} = \begin{matrix}( & {#C_{ns}(𝔽_{q})−#S−(2d−4) \atop u−(2d−4)} & ) \\ ( & {#C_{ns}(𝔽_{q})−#S \atop u} & ) \end{matrix}

= \frac{(u − 2d + 5) · (u − 2d + 6) ⋯ u}{(#C_{ns}(𝔽_{q}) − #S − 2d + 5) ⋯ (#C_{ns}(𝔽_{q}) − #S)} .

We have

p_{D} ∈ [(\frac{u − d + 3}{#C_{ns}(𝔽_{q}) − #S} )^{d−2}, (\frac{u}{#C_{ns}(𝔽_{q}) − #S − d + 3})^{d−2}]  (5)

and

p_{D_{1},D_{2}} ∈ [(\frac{u − 2d + 5}{#C_{ns}(𝔽_{q}) − #S} )^{2d−4}, (\frac{u}{#C_{ns}(𝔽_{q}) − #S − 2d + 5})^{2d−4}] . (6)

Let N be the number of divisors in 𝔡 which split completely into distinct points of C_{ns}(𝔽_{q}) and contain Q and exactly one point from S. Note that

N ∈ [\frac{1}{2(d − 1)!} · #S, #S]  (7)

by assumption.^{3} For the probability p we obtain:

p ≥ N · (\frac{u − d + 3}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} − \frac{1}{2} · N^{2} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S − 2d + 5})^{2d−4}

∈ N · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} · (1 + O(\frac{1}{u})) + O(N^{2} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{2d−4})

Now

N · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} ∈ Θ(#S · q^{−1}),

(\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} · \frac{1}{u} ∈ Θ(#S · q^{−2+ \frac{1}{d−2}} ),

N^{2} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{2d−4} ∈ Θ(#S^{2} · q^{−2}) .

We have #S · q^{−2+ \frac{1}{d−2}} ∈ O(#S^{2} · q^{−2}) as q^{\frac{1}{d−2}} ∈ O(#S) by assumption. So there exists some constant C > 0 (depending only on c) such that

p ≥ N · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} − C · (N · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2})^{2} . (8)

In particular

p ≳ \frac{c^{d−2}}{2(d − 1)!} · \frac{#S}{q} ·

□

3We would like to alert the reader here to the meaning of the three previous statements and the following statements: The statements in (5) and (6) say that the numbers p_{D} and p_{D_{1},D_{2}} lie in certain intervals. Likewise, (7) says that N lies in an interval. But (7) also has this meaning: The function N on the set of isomorphism classes considered in the proposition lies in a set of functions on the set of isomorphism classes. In the statements below, until the end of the proof, we always make assertions on functions on the set of isomorphism classes. Additionally, one can also consider isomorphism classes of tuples consisting of data as in the proposition and a divisor D as above or isomorphism classes of tuples consisting of data as in the proposition and a pair of divisors (D_{1}, D_{2}) as above. Then (5) and (6) can also be interpreted as assertions on functions. (The indices D and D_{1}, D_{2} in p_{D} and p_{D_{1},D_{2}} now denote part of an argument of the functions.) Such a point of view on p_{D} and p_{D_{1},D_{2}} is of importance in the proof of Proposition 18 below.

Proposition 18 Let c > 0 be fixed. We consider a set of isomorphism classes of tuples consisting of: a curve C/𝔽_{q}, a plane model C_{pm} of degree d of C, a birational morphism π : C ⟶ C_{pm} and a subset S ⊆ C_{ns}(𝔽_{q}) such that q^{1− \frac{1}{d−2}} ∈ o(#S) and #S ∈ o(q). Given such a tuple, we set u := ⌈c · q^{1− \frac{1}{d−2}} ⌉.

Then the following holds: For a random subset U of C_{ns}(𝔽_{q}) − S which is uniformly randomly distributed among all subsets of cardinality u, the probability that there are at least \frac{c^{d−2}}{5(d−1)!^{2}} · #S points Q ∈ C_{ns}(𝔽_{q}) − (S ∪ U) such that there exists a divisor in 𝔡 which

- splits completely into distinct points of C_{ns}(𝔽_{q}),

- contains Q, exactly one point of S and otherwise only points of U,

is asymptotically equal to 1 for q ⟶ ∞.

Proof. Let Q be the set of points Q ∈ C_{ns}(𝔽_{q}) − S such that there exist at least \frac{1}{2(d−1)!} · #S divisors in 𝔡 which split completely into distinct points of C_{ns}(𝔽_{q}), contain Q and exactly one point from #S. By Proposition 16, #Q ≳ \frac{1}{2(d−1)!}q. We only consider points from Q.

For such a point Q let A_{Q} be the event that there exists at least one divisor which split completely into distinct points of C_{ns}(𝔽_{q}), contains Q, exactly one point from #S and otherwise points from U. (We do not impose a condition on Q not being in U.)

We have

𝔼[ ∑_{Q∈Q} χ_{A_{Q}}] = ∑_{Q∈Q} ℙ[A_{Q}] ≳ \frac{c^{d−2}}{4 · (d − 1)!^{2}} · #S  (9)

by Proposition 17.

Below we show that the standard deviation of ∑_{Q∈Q} χ_{A_{Q}} is in o(𝔼[∑_{Q∈Q} χ_{A_{Q}}]). Let us for the moment assume that we have already proven this result, and let us see how the statement in the proposition then follows. With the Chebyshev inequality and (9) we conclude that with a probability which is asymptotically equal to 1 for q ⟶ ∞, we have

∑_{Q∈Q} χ_{A_{Q}} ≥ \frac{c^{d−2}}{\frac{9}{2} · (d − 1)!^{2}} · #S ·

Recall that ∑_{Q∈Q} χ_{A_{Q}} is a lower bound on the number of points Q ∈ C_{ns}(𝔽_{q}) − S such that there exists a divisor in 𝔡 which splits completely into distinct points of C_{ns}(𝔽_{q}), contains Q, exactly one point from S and otherwise only points from U. Now, such a point Q might also be contained in U. As however #U ∈ o(#S) by assumption, we conclude:

With a probability which is asymptotically equal to 1, there exist at least \frac{c^{d−2}}{5·(d−1)!^{2}} · #S points in Q ∈ C_{ns}(𝔽_{q}) − (S ∪ U) such that there exists a divisor in 𝔡 which splits completely into distinct points of C_{ns}(𝔽_{q}), contains Q, exactly one point from S and otherwise only points from U. This is the desired result.

It remains to be shown that the standard deviation of ∑_{Q∈Q} χ_{A_{Q}} is in o(𝔼[∑_{Q∈Q} χ_{A_{Q}}]).

The variance of 𝔼[∑_{Q∈Q} χ_{A_{Q}}] is

\begin{aligned}& 𝔼[( ∑_{Q∈Q} χ_{A_{Q}})^{2}] − (𝔼[ ∑_{Q∈Q} χ_{A_{Q}}])^{2} \\ = & ∑_{Q_{1},Q_{2}∈Q}(ℙ[A_{Q_{1}} ∩ A_{Q_{2}}] − ℙ[A_{Q_{1}}] · ℙ[A_{Q_{2}}]) \\ ≤ & 𝔼[ ∑_{Q∈Q} χ_{A_{Q}}] + \\ & ∑_{Q_{1},Q_{2}∈Q,Q_{1}≠Q_{2}} (ℙ[A_{Q_{1}} ∩ A_{Q_{2}}] − ℙ[A_{Q_{1}}] · ℙ[A_{Q_{2}}]) . \end{aligned} (10)

We now wish to establish a suitable upper bound on ℙ[A_{Q_{1}} ∩ A_{Q_{2}}] − ℙ[A_{Q_{1}}] · ℙ[A_{Q_{2}}] for Q_{1} ≠ Q_{2}. We use (8) to obtain a lower bound on the subtrahend. (Note that q^{\frac{1}{d−2}} ≤ q^{1− \frac{1}{d−2}} ∈ o(#S) by assumption and because d ≥ 4. Therefore the assumptions of Proposition 17 are satisfied.)

The task is now to establish a suitable upper bound on the minuend. Let Q_{1}, Q_{2} ∈ Q with Q_{1} ≠ Q_{2} be fixed. Let for two divisors D_{1}, D_{2} ∈

𝔡, each splitting completely into distinct points of C_{ns}(𝔽_{q}), such that D_{1} contains Q_{1} and D_{2} contains Q_{2} and both contain a point from S, p_{D_{1},D_{2}} be the probability that the remaining points in both divisors are all contained in U.

Clearly,

ℙ[A_{Q_{1}} ∩ A_{Q_{2}}] ≤ ∑_{D_{1},D_{2}} p_{D_{1},D_{2}} ,

where the sum ranges over all pairs of divisors just specified.

For an upper bound on p_{D_{1},D_{2}}, there are two cases to consider, depending on whether the two lines meet in C_{ns}(𝔽_{q}) − S or not. In the first case, D_{1} and D_{2} have one point outside of S in common, and we write D_{1} ∩ D_{2} ⊈ S. In the second case, they do not have a point outside of S in common, and we write D_{2} ∩ D_{2} ⊆ S.

We consider the case that the two lines meet in C_{ns}(𝔽_{q}) − S first. In this case, D_{1} ∪ D_{2} contains 2d − 5 points in C_{ns}(𝔽_{q}) − (S ∪ {Q_{1}, Q_{2}}). We have

p_{D_{1},D_{2}} = \begin{matrix}( & {#C_{ns}(𝔽_{q})−#S−(2d−5) \atop u−(2d−5)} & ) \\ ( & {#C_{ns}(𝔽_{q})−#S \atop u} & ) \end{matrix}

= \frac{(u − 2d + 6) · (u − 2d + 7) ⋯ u}{(#C_{ns}(𝔽_{q}) − #S − 2d + 6) ⋯ (#C_{ns}(𝔽_{q}) − #S)} ·

Thus

p_{D_{1},D_{2}} ≤ (\frac{u}{#C_{ns}(𝔽_{q}) − #S − 2d + 6})^{2d−5} ∈ O(q^{\frac{−(2d−5)}{d−2}} ) = O(q^{−2+ \frac{1}{d−2}} )

in this case.

Note that for every divisor D_{1} ∈ 𝔡 which contains exactly one point from S and Q_{1}, there exist at most d − 2 divisors D_{2} ∈ 𝔡 with D_{1} ∩ D_{2} ⊈ S which contain exactly one point from S and Q_{2}. (D_{2} is determined by its intersection with D_{1}.) Thus

∑_{\begin{matrix}D_{1}, D_{2} with \\ D_{1} ∩ D_{2} ⊈ S \end{matrix}} p_{D_{1},D_{2}} ∈ O(#S · q^{−2+ \frac{1}{d−2}} ) .  (11)

We now consider pairs of divisors of the second type. For such divisors D_{1}, D_{2}, we have

p_{D_{1},D_{2}} = \begin{matrix}( & {#C_{ns}(𝔽_{q})−#S−(2d−4) \atop u−(2d−4)} & ) \\ ( & {#C_{ns}(𝔽_{q})−#S \atop u} & ) \end{matrix}

= \frac{(u − 2d + 5) · (u − 2d + 6) ⋯ u}{(#C_{ns}(𝔽_{q}) − #S − 2d + 5) ⋯ (#C_{ns}(𝔽_{q}) − #S)} ·

Thus

\begin{matrix}p_{D_{1},D_{2}} ≤ & (\frac{u}{#C_{ns}(𝔽_{q}) − #S − 2d + 5})^{2d−4} \\ ∈ & (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{2d−4} · (1 + O(\frac{1}{q})) . \end{matrix}

Let for i = 1, 2 N_{i} be the number of divisors which split completely into distinct points of C_{ns}(𝔽_{q}), contain Q_{i} and exactly one element from S. Then

∑_{\begin{matrix}D_{1}, D_{2} with \\ D_{1} ∩ D_{2} ⊆ S \end{matrix}} p_{D_{1},D_{2}} ≤ N_{1}N_{2}(\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{2d−4} · (1 + C_{1} · \frac{1}{q}) (12)

for some constant C_{1} > 0.

Altogether, we obtain by (8), (11) and (12):

ℙ[A_{Q_{1}} ∩ A_{Q_{2}}] − ℙ[A_{Q_{1}}] · ℙ[A_{Q_{2}}]

≤ C_{0} · #S · q^{−2+ \frac{1}{d−2}} + N_{1}N_{2}(\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{2d−4} · (1 + C_{1} · \frac{1}{q})−

(N_{1} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} − C_{2} · (N_{1} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2})^{2}) ·

(N_{2} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2} − C_{2} · (N_{2} · (\frac{u}{#C_{ns}(𝔽_{q}) − #S} )^{d−2})^{2})

for constants C_{0}, C_{1}, C_{2} > 0. This is in

O(#S · q^{−2+ \frac{1}{d−2}} + #S^{2} · q^{−3}) ⊆ O(#S · q^{−2+ \frac{1}{d−2}} ) .

Because of this and (10) the variance of ∑_{Q∈Q} χ_{A_{Q}} is in

\begin{matrix}O(𝔼[ ∑_{Q∈Q} χ_{A_{Q}}] + #S · q^{\frac{1}{d−2}} ) \\ ⊆ O(𝔼[ ∑_{Q∈Q} χ_{A_{Q}}]) + o(#S^{2}) ⊆ o(𝔼[ ∑_{Q∈Q} χ_{A_{Q}}]^{2}) . \end{matrix}

Here, the second inclusion follows from (9). We obtain that the standard deviation of ∑_{Q∈Q} χ_{A_{Q}} is in o(𝔼[∑_{Q∈Q} χ_{A_{Q}}]), and this completes the proof. □

Proof of Proposition 15

We show now how Proposition 15 can be obtained with Proposition 18.

We set c := (5 · (d − 1)!^{2})^{\frac{1}{d−2}} , and we apply the proposition with subsets S ⊆ C(𝔽_{q}) such that #S ≥ log(q) · q^{1− \frac{1}{d−2}} and #S ≤ 2 · q^{1− \frac{1}{g} + \frac{1}{(d−2)g}}. Now Proposition 15 says that there exists a function f from the set of prime powers to ℝ_{>0} which converges to 1 such that the following holds: For all prime powers q and all isomorphism classes as indicated in Proposition 18 over 𝔽_{q} the probability that there are at least #S points Q ∈ C_{ns}(𝔽_{q}) − (S ∪ U) such that there exists a divisor in 𝔡 which splits completely into distinct points of C_{ns}(𝔽_{q}), contains Q, exactly one point of S and otherwise points of U is ≥ f(q) (cf. subsection “Notation and representation” in the introduction). Let us fix such a function f.

To analyze Step 1, we set S := F_{0} and U := F_{1}. Note that the assumptions on the size of S are satisfied because #F_{0} = ⌈log(q) · q^{1− \frac{1}{d−2}} ⌉. Note also that the statement in the proposition is on divisors of the form P_{1} + ⋯ + P_{d−2} + P + Q with P_{i} ∈ F_{1}, P ∈ F_{0} and Q ∈ C(𝔽_{q}) − (F_{0} ∪ F_{1}).

However, the conclusion of course also remains valid if we consider more divisors. The conclusion is then that the probability that a particular repetition of Step 1 leads to success is ≥ f(q).

For Steps ≥ 2, we set S := F ∪ V (T ) and U := G. It is obvious that the assumptions are satisfied, and in the algorithm we consider exactly the same divisors as in the proposition. The conclusion is the same as in Step 1: The probability that a particular repetition leads to success is ≥ f(q).

References

[1] C. Diem. An Index Calculus Algorithm for Plane Curves of Small Degree. In F. Hess, S. Pauli, and M. Pohst, editors, Algorithmic Number Theory — ANTS VII, LNCS 4076, pages 543 – 557, Berlin, 2006. Springer.

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

[3] C. Diem. On the discrete logarithm problem in class groups of curves. Math.Comp., 80:443 – 475, 2011.

[4] C. Diem. On the notion of bit complexity. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 103:35–52, 2011. In the “Complexity Column”.

[5] C. Diem and E. Thomé. Index calculus in class groups of nonhyperelliptic curves of genus three. J. Cryptology, 21:593–611, 2008.

[6] 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.

[7] R. Hartshorne. Algebraic Geometry. Springer-Verlag, 1977.

[8] A. Hefez. Non-reflexive curves. Compositio Math., 69:3–35, 1989.

[9] A. Hefez and S. Kleiman. Notes on the duality of projective varieties. In Geometry today (Rome, 1984), volume 60 of Progr. Math., pages 143–183. Birkhäuser, 1985.

[10] F. Heß. Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symb. Comput., 33, 2002.

[11] S. Kleiman. The enumerative theory of singularities. In Real and complex singularities (Proc. Ninth Nordic Summer School/NAVF Sympos. Math., Oslo, 1976), pages 297–396. Sijthoff and Noordhoff, Alphen aan den Rijn, 1977.

[12] V.K. Murty and J. Scherk. Effective versions of the Chebotarev density theorem for funciton fields. C. R. Acad. Sci., 319:523–528, 1994.

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

[14] J. Neukirch. Algebraische Zahlentheorie. Springer-Verlag, 1991.

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

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

[17] N. Thériault. Index calculus attack for hyperelliptic curves of small genus. In Advances in Cryptology — ASIACRYPT 2003, volume 2894 of LNCS, pages 75–92. Springer-Verlag, 2003.

[18] R. Walker. Algebraic Curves. Springer-Verlag, 1978.

[19] A. Wallace. Tangency and duality over arbitrary fields. Proc. Lond. Math. Soc. (3), 6:321–342, 1956.

[20] H. Wieland. Finite Permutation Groups. Academic Press, New York, 1964.

Claus Diem University of Leipzig Mathematical Institute Augustusplatz 10 04109 Leipzig Germany diem@math.uni-leipzig.de