On the discrete logarithm problem in elliptic curves II

Claus Diem

September 23, 2013

Abstract

We continue our study on the elliptic curve discrete logarithm problem over finite extension fields. We show, among others, the following results:

For sequences of prime powers (q_{i})_{i∈ℕ} and natural numbers (n_{i})_{i∈ℕ} with n_{i} ⟶ ∞ and \frac{n_{i}}{log(q_{i})^{2}} ⟶ 0 for i ⟶ ∞, the discrete logarithm problem in the groups of rational points of elliptic curves over the fields 𝔽_{q_{i}^{n_{i}}} can be solved in subexponential expected time (q_{i}^{n_{i}})^{o(1)}.

Let a, b > 0 be fixed. Then the problem over fields 𝔽_{q^{n}}, where q is a prime power and n a natural number with a · log(q)^{1/3} ≤ n ≤ b · log(q), can be solved in an expected time of e^{O(log(q^{n})^{3/4})}.

1 Introduction

In our previous work [Die11b] we have shown that there exist sequences of finite fields over which the elliptic curve discrete logarithm problem can be solved in subexponential expected time in the bit-length of the input.

In this work, we strengthen the results from [Die11b]. We show that for larger classes of ground fields the problem can still be solved in subexponential expected time.

Recall that the main result from [Die11b] is as follows.

Theorem 1 The discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}} can be solved in an expected time of

e^{O(max(log(q), n^{2}))} .

Here and in the following, q is always a prime power and n a natural number.

It follows from this theorem that for any two sequences (q_{i})_{i∈ℕ} and (n_{i})_{i∈ℕ} of prime powers and natural numbers with n_{i} ⟶ ∞ and \frac{n_{i}}{log(q_{i})} ⟶ 0 for i ⟶ ∞, the discrete logarithm problem in the groups of rational points of elliptic curves over the fields 𝔽_{q_{i}^{n_{i}}} can be solved in an expected time of (q_{i}^{n_{i}})^{o(1)}.

The main result of this work is the following stronger theorem.

Theorem 2 The discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}} can be solved in an expected time of

e^{O(max(log(q), n·log(q)^{1/2}, n^{3/2}))} .

Note here that

max(log(q), n · (log(q))^{1/2}, n^{3/2}) = \{ \begin{matrix}log(q) & for n ≤ log(q)^{1/2} \\ n · (log(q))^{1/2} & for log(q)^{1/2} ≤ n ≤ log(q) \\ n^{3/2} & for log(q) ≤ n . \end{matrix}

Theorem 2 gives the following results.

1. Let sequences of prime powers (q_{i})_{i∈ℕ} and natural numbers (n_{i})_{i∈ℕ} with q_{i} ⟶ ∞ and \frac{n_{i}}{log(q_{i})^{2}} ⟶ 0 for i ⟶ ∞ be given. Then the discrete logarithm problem in the groups of rational points of elliptic curves over the fields 𝔽_{q_{i}^{n_{i}}} can be solved in an expected time of

(q_{i}^{n_{i}})^{o(1)} .

2. Let β ∈ [\frac{1}{2}, 1] and a, b > 0 be fixed. Let

α := \frac{1}{2β + 1} and γ := 1 − \frac{1}{2} \frac{1}{β + 1} = \frac{β + \frac{1}{2}}{β + 1} .

Then the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}} with

a · log(q)^{α} ≤ n ≤ b · log(q)^{β}  (1)

can be solved in an expected time of

e^{O(log(q^{n})^{γ})} .

Note that α ≤ \frac{1}{2} (with equality if β = \frac{1}{2}), and γ is maximal if α = β = \frac{1}{2}, and then it is equal to \frac{2}{3}.

As a special case we obtain that for a, b > 0 the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}} with

a · log(q)^{1/3} ≤ n ≤ b · log(q)

can be solved in an expected time of e^{O(log(q^{n})^{3/4})}.

3. Let β ∈ [1, 2) and a, b > 0 be fixed. Let

α := \frac{2 − β}{3β} and γ := \frac{3}{2} · \frac{β}{1 + β} .

Then the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}} with

a · log(q)^{α} ≤ n ≤ b · log(q)^{β}

can be solved in an expected time of

e^{O(log(q^{n})^{γ})} .

The first statement follows immediately from Theorem 2.

The derivation of the second statement from Theorem 2 is as follows: We have β = \frac{γ− \frac{1}{2}}{1−γ} and α = \frac{1}{γ} − 1.

The first inequality in (1) is equivalent to n ≥ a · log(q)^{\frac{1}{γ} −1}, and this is equivalent to \frac{1}{a^{γ}} · (n log(q))^{γ} ≥ log(q).

The second inequality is equivalent to b^{1−γ} · log(q)^{γ− \frac{1}{2}} ≥ n^{1−γ}, and this is equivalent to b^{1−γ} · (n log(q))^{γ} ≥ n · log(q)^{1/2}.

Additionally, except if q = 2, we have log(q) ≥ log(q)^{β} ≥ \frac{1}{b} · n and thus n · log(q)^{1/2} ≥ \frac{1}{b} · n^{3/2}.

The results now follow with Theorem 2.

We now show how the third statement follows from Theorem 2. We have β = \frac{2γ}{3−2γ} and – as above – α = \frac{1}{γ} − 1.

For the range a · log(q)^{α} ≤ n ≤ log(q), the result follows from the second point, so we consider the range log(q) ≤ n ≤ b · log(q)^{β}. We have n ≤ b · log(q)^{\frac{2γ}{3−2γ}}, that is, n^{\frac{3}{2} −γ} ≤ b^{\frac{3}{2} −γ} · log(q)^{γ}. With other words: n^{\frac{3}{2}} ≤ b^{\frac{3}{2} −γ} · (n · log(q))^{γ}.

As an application of Theorem 2 we now consider the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields of a fixed characteristic p. We first remark that Theorem 2 does not give a non-trivial result if q is set to p and n is set to the absolute extension degree of the ground field. We therefore consider a factorization of the absolute extension degree in the form mn, that is, we write the cardinality of the ground field in the form p^{mn}. We can then regard both m and n as the extension degree. One sees that it is advantageous to regard n as the extension degree provided that n ≤ m and m as the extension degree otherwise. In this way one obtains:

Theorem 3 Let p be a fixed prime number. Then the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{p^{mn}} can be solved in an expected time of

e^{O(max(m, n, min(m·n^{1/2}, n·m^{1/2})))} .

Here we have

max(m, n, min(m · n^{1/2}, n · m^{1/2})) = \{ \begin{matrix}m & for n ≤ m^{1/2} \\ n · m^{1/2} & for m^{1/2} ≤ n ≤ m \\ m · n^{1/2} & for n^{1/2} ≤ m ≤ n \\ n & for m ≤ n^{1/2} . \end{matrix}

For any fixed prime number p, Theorem 3 gives the following results:

4. Let (m_{i})_{i∈ℕ} and (n_{i})_{i∈ℕ} with m_{i}, n_{i} ⟶ ∞ for i ⟶ ∞. Then the discrete logarithm problem in the groups of rational points of elliptic curves over the finite fields 𝔽_{p^{m_{i}n_{i}}} can be solved in an expected time of

(p^{m_{i}n_{i}})^{o(1)} .

5. Let α ≥ 3 and a, b > 0. Then the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{p^{mn}} with

m ≤ a · n^{α} and n ≤ b · m^{α}

can be solved in an expected time of

e^{O(log(p^{mn})^{1− \frac{1}{1+α}})} .

Just as Statement 1 above, Statement 4 is again immediate.

So we consider the last statement. Let α ≥ 3. Note first that 1 − \frac{1}{1+α} = \frac{α}{1+α} = _{\frac{1}{1+ \frac{1}{α}}}. We have m^{1+ \frac{1}{α}} ≤ a^{1/α} · mn and therefore m ≤ a^{\frac{1}{1+α}} · (mn)^{\frac{α}{1+α}}.

Similarly, n ≤ a^{\frac{1}{1+α}} · (mn)^{\frac{α}{1+α}}. Moreover, 1 − \frac{1}{1+α} ≥ \frac{3}{4}. Thus if n ≤ m, then n · m^{1/2} ≤ (mn)^{3/4} ≤ (mn)^{\frac{α}{1+α}}. Analogously, if m ≤ n, then m · n^{1/2} ≤ (mn)^{\frac{α}{1+α}}.

Some more information on the results

We give here some more information on the precise meaning of the statements above and similar statements throughout this article.

First, we choose some concrete representation of the “abstract input instances” (elliptic curves E over finite fields K and elements a, b ∈ E(K) with a ∈ ⟨b⟩) by bit-strings. Every “abstract instance” is then given by at least one and finitely many bit-strings. Concretely, we represent elliptic curves by Weierstraß equations, as usual. We also choose some (uniform) randomized model of computation with an appropriate complexity measure, for example a usual randomized RAM model with logarithmic cost function or a randomized Turing model.

For a function f from some infinite countable set S to ℝ_{>0}, we define the sets O(f), Õ, o(f) and Poly(f) as usual (for the latter see also [Die11b]). We note here that it makes no difference if S is a subset of ℕ or not.

The assertion in Theorem 1 is then as follows: There exists a machine in the given model and a constant C > 0 such that, if the machine is applied to an instance of the elliptic curve discrete logarithm problem over a field 𝔽_{q^{n}}, the expected running time is bounded by e^{C·max(log(q),n^{2})}. The assertions in Theorem 2 and Theorem 3 are analogous. We stress that the expected value concerns only the internal choices of the computation; there is no averaging over input classes.

Statement 1 means the following: Let (q_{i})_{i∈ℕ} and (n_{i})_{i∈ℕ} be given as indicated. Then there exists a randomized machine and a sequence (ϵ_{i})_{i∈ℕ} with ϵ_{i} ⟶ 0 for i ⟶ ∞ such that the expected running time of the machine if applied to an instance over 𝔽_{q_{i}^{n_{i}}} is bounded by (q_{i}^{n_{i}})^{ϵ_{i}}. Statement 4 is again analogous.

As usual, throughout this article we use the word “algorithm” instead of “machine”. Also as usual, we use the word “algorithm” in an informal way when we outline a computation.

Outline

Just as the algorithm in [Die11b], the algorithm for Theorem 2 is based on the usual index calculus or relation generation and linear method. Again we use multivariate polynomial systems over 𝔽_{q} to obtain relations. The main conceptual difference between the new algorithm and the previous algorithm is that we enlarge the factor base. This enlargement causes some difficulties in the analysis of the algorithm, and in order to complete the analysis we further modify the definition of the factor base. We also employ a new algorithm to find decompositions. Otherwise the index calculus algorithm in [Die11b] is not changed.

Below we outline a preliminary algorithm, and on the basis of this algorithm, we discuss under various heuristic assumptions why one should be able to obtain an expected running time of e^{O(max(log(q),n·log(q)^{1/2}))}. In the course of this work, we will change the algorithm in various ways. Unfortunately, even with a modified algorithm we cannot prove that one can obtain the expected running time one might expect by heuristic considerations.

Indeed, in odd characteristic we can only complete the analysis under the condition that c^{n} ≤ q for a suitable constant c > 0. In even characteristic the situation is more fortunate and we can complete the analysis if n^{c} ≤ q for a suitable constant c > 0. This does however not lead to an improvement over the result in Theorem 3 applied to fields of even characteristic.

The index calculus algorithm we employ has the same overall structure as the one in [Die11b] (see subsection 2.3 of that work). The changes we perform concern the definition of the factor base (Steps 4 and 5 of that algorithm) and the relation generation (Step 6), where a new decomposition algorithm is employed. Because the overall structure of the algorithm stays the same, we will focus on the parts of the index algorithm which need to be changed.

In the next section, we give the new algorithm for the constructions leading to the definition of the factor base. In Section 3 we formulate a decomposition problem adapted to the new situation and give an algorithm to solve the problem. In the fourth and last section, we prove that under suitable conditions on n and q the probability that a uniformly randomly distributed point P ∈ E(𝔽_{q^{n}}) leads to a relation between P and factor base elements is large enough. In the last part of this section, we indicate how Theorem 2 can be obtained. Additionally, in an appendix we correct two misprints in our previous work [Die11b].

Throughout the article we use the same notation as in our previous work, with the exception that we now denote an affine defining polynomial for the elliptic curve by f(x, y).

The application of the scalar restriction functor, that is, the formation of Weil restrictions, is crucial in this work. Furthermore, many arguments in this work are based on the consideration of tangent spaces. Background information on these topics is given at the end of this section. The reader should also be familiar with the first two sections of [Die11b]. Additionally, we assume some familiarity with toric geometry and its application to solving polynomial systems as given in [Ful93], [CLO05] and in particular in [Roj99].

A preliminary algorithm

The algorithm follows the usual “index calculus” strategy: After some preliminary computations to determine the group structure, we fix a so-called factor base, generate relations and finally solve the discrete logarithm problem via linear algebra.

Just as in [Die11b], the factor base is defined in an algebraic way, and the relations are obtained by solving systems of multivariate polynomial equations over 𝔽_{q}.

Let some instance of the problem with a prime power q, a natural number n ≥ 2 and an elliptic curve E/𝔽_{q^{n}} be given, where E is (as usual) given by an affine Weierstraß equation in x and y with neutral element the point at infinity.

The definition of the factor base and the relation generation are as follows:

Let m be some natural number at most n, which will be optimized later, and let d := ⌈\frac{n}{m}⌉ and δ := dm − n.

We choose some d-dimensional vector subspace U of the 𝔽_{q}-vector space 𝔽_{q^{n}} and define the factor base by

F := {P ∈ E(𝔽_{q^{n}}) | x(P) ∈ U} .

Furthermore, if n is not divisible by m (that is, δ ≠ 0), we choose a (d − 1)- dimensional vector subspace U′ of U and set

F′ := {P ∈ E(𝔽_{q^{n}}) | x(P) ∈ U′} .

Given some element P ∈ E(𝔽_{q^{n}}), we want to find a relation

P_{1} + ⋯ + P_{m} = P

with P_{i} ∈ F′ for i = 1, …, δ and P_{i} ∈ F for i = δ +1, …, m. The key idea is again to find such relations by solving systems of polynomial equations over 𝔽_{q}. One possibility to obtain such a system is via summation polynomials.

Recall that the (m + 1)^{th} summation polynomial with respect to the covering x_{|E} : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} is an irreducible multihomogeneous polynomial S_{m+1} ∈ 𝔽_{q^{n}}[X_{1}, Y_{1}, …, X_{m+1}, Y_{m+1}] such that for P_{1}, …, P_{m+1} ∈ E(\overline{𝔽}_{q}), P_{1} + ⋯ + P_{m+1} = 0 if and only if s_{m+1}(x_{|E}(P_{1}), …, x_{|E}(P_{m+1})) = 0; see Proposition 2.1 and Section 3 of [Die11b]. The (m + 1)^{th} affine summation polynomial with respect to x_{|E} is the dehomogenization of this polynomial with respect to Y_{1}, …, Y_{m}. This is a polynomial s_{m+1}(x_{1}, …, x_{m+1}) ∈ 𝔽_{q^{n}}[x_{1}, …, x_{m+1}].

We expand the variables (or coordinates) x_{1}, …, x_{m} over 𝔽_{q} with respect to the basis. Then for i = 1, …, δ and i = δ + 1, …, m we restrict the resulting systems of coordinates to U′ and U, respectively. In this way the polynomial s_{m+1}(x_{1}, …, x_{m}, x(P)) gives rise to a system of n polynomials in n variables. The polynomial s_{m+1}(x_{1}, …, x_{m}, x(P)) has degree 2^{m−1} in each variable and therefore total degree at most m · 2^{m−1}. Therefore each polynomial in the system has degree at most m · 2^{m−1}. It follows that “with multiplicities” the system has at most (m · 2^{m−1})^{n} = m^{n} · 2^{(m−1)·n} isolated solutions over 𝔽_{q}. Here by an isolated solution we mean an isolated point of the scheme defined by the system. (This can be seen by intersection theory in ℙ_{𝔽_{q}}^{n}, similarly to statement a) in Proposition 2.5 of [Die11b].)

Now, with an algorithm by M. Rojas ([Roj99]), one can compute a list of solutions of the system over 𝔽_{q} containing all isolated solutions over 𝔽_{q} in an expected time of Poly(m^{n} · 2^{n·(m−1)} · log(q)) = Poly(e^{mn} · log(q)).

Let us assume that for varying P, most solutions over 𝔽_{q} of these systems are indeed isolated. It is reasonable to estimate the size of F as roughly q^{d} and the size of F′ as roughly q^{d−1}. This indicates that the expected value of relations obtained per try is in O(\frac{1}{m!}).

Disregarding the possibility that some of the relations generated might be linearly dependent, we need roughly q^{d} relations. This indicates an expected running time of

Poly(m! · e^{nm+log(q)·d}) = Poly(e^{nm+log(q)· \frac{n}{m}}) .

for the relation generation part.

The expected running time for the linear algebra part is merely Poly(e^{log(q)·d}).

Now for m := min(⌈\sqrt{log(q)}⌉, n), we obtain, again on the basis of the above heuristic arguments, a total expected running time of

Poly(e^{max(log(q),n·\sqrt{log(q)})}) .

We stress again that we have used various heuristic assumptions. The goal of the rest of this work is to modify the algorithm in such a way that we can indeed prove the claimed expected running time for large input classes. As already stated, we are however not able to establish the desired expected running time for all instances of the problem.

Weil restrictions and the scalar restriction functor

Let us recall the definition of the scalar restriction functor with respect to a finite field extension.

Let K|k be a finite field extension. Now let X be a quasi-projective K-scheme of finite type. Then a representing object of the contravariant functor Z ↦ Hom_{K}(Z ×_{k} K, X) from the category of k-schemes to the category of sets is called the Weil restriction of X with respect to K|k. We denote the representing k-scheme by Res_{k}^{k}(X); as usual we also fix a corresponding natural transformation. A reformulation of the definition is: The Weil restriction of X with respect to K|k is a k-scheme Res_{k}^{K}(X) together with a morphism u : Res_{k}^{K}(X)_{K} = Res_{k}^{K}(X)×_{k} K ⟶ X satisfying the following universal property: For any k-scheme and any K-morphism α : Z_{K} = Z ×_{k} K ⟶ X there exists a unique k-morphism β : Z ⟶ Res_{k}^{K}(X) with α = u ∘ β_{K}. We denote β by α_{⊚}. Now, the formation of the Weil restriction defines a functor from the category of quasi-projective Kschemes to the category of quasi-projective k-schemes; this functor is called the scalar restriction functor. Furthermore, if X a group scheme, so is the Weil restriction in an obvious way.

In this work, we very often use Weil restrictions of the affine line 𝔸_{K}^{1} = Spec(K[x]). Note here that Res_{k}^{K}(𝔸_{K}^{1})(k) ≃ 𝔸^{1}(K) = K. One sees easily the following: Let b_{1}, …, b_{n} be a k-basis of K. Then 𝔸_{k}^{n} = Spec(k[x_{1}, …, x_{n}]) together with the universal morphism 𝔸_{K}^{n} ⟶ 𝔸_{K}^{1}, given on Z-valued points for any K-scheme Z by P ↦ x_{1}(P)b_{1} + ⋯ + x_{n}(P)b_{n}, is a Weil restriction of 𝔸_{k}^{1} with respect to K|k (as a group variety). The choice of a k-basis of K of course corresponds to choosing a k-homomorphism K ≈ k^{n}.

We would like to have an explicit and canonical description of the Weil restriction of 𝔸_{k}^{1} which does not depend on the choice of a basis. For this, let us define for any finite dimensional k-vector space V the polynomial algebra k[V] in the usual way:

k[V] := ⨁_{i=0}^{∞} V ⨂ i_{sym}

For some finite dimensional k-vector space V, let

𝔸_{k}[V] := Spec(k[V^{∨}]) ,

where V^{∨} is the dual space of V. Now for any k-algebra A, we have 𝔸_{k}[V](A) ≃ Hom_{k}(V^{∨}, A) ≃ A ⊗_{k} V in a natural way. Now, A ⊗_{k} V is a k-vector space and therefore in particular an abelian group. We obtain in this way a commutative group structure on 𝔸_{k}[V]. Clearly, 𝔸_{k}[V](k) is isomorphic to (V, +) itself. The association V ↦ 𝔸_{k}[V] gives rise to a covariant functor from the category of finite dimensional vector spaces over k to the category of affine group varieties over k. Here, an injective homomorphism U ⟶ V gives a closed embedding 𝔸_{k}[U] ⟶ 𝔸_{k}[V], and in particular for a vector subspace U of V, 𝔸_{k}[U] is a group subvariety of 𝔸_{k}[V].

As a special case of the preceding we have natural isomorphisms 𝔸_{k}[K](A) ≃ A⊗_{k}K for any k-algebra A. Therefore 𝔸_{k}[K] is in a natural way a Weil restriction of 𝔸_{K}^{1} with respect to K|k. We remark that the universal morphism u : 𝔸_{k}[K] ×_{k} K ⟶ 𝔸_{K}^{1} is given as follows: 𝔸_{k}[K] ×_{k} K is the affine scheme defined by the K-algebra k[K^{∨}]⊗_{k} K ≃ ⨁_{i=0}^{∞}(K^{∨})^{⊗_{sym}i} ⊗_{k} K, and the universal morphism corresponds to a homogeneous element of degree 1 in the algebra, that is, to an element of K^{∨} ⊗_{k} K. This vector space is naturally isomorphic to the vector space of endomorphisms of K as a vector space over k. The universal morphism is the element of K^{∨} ⊗_{k} K corresponding to the identity in this space.

We also use Weil restrictions with respect to flat coverings, that is, finite and flat morphisms. For this and also for other aspects of the scalar restriction functor we refer to subsection 4.1 of [Die11b].

Tangent spaces and ramification

We make frequent use of homomorphisms between tangent spaces to address whether morphisms of schemes over fields are unramified at rational points. For the convenience of the reader and because we could not find a suitable reference, we make some general remarks here.

Let k be a field.

Let X be a k-scheme of finite type and P a k-rational point of X. Denoting by κ(P) the residue field at P, we have a canonical isomorphism k ≃ κ(P). We use the latter notation if we regard k as an O_{X,P} -algebra.

The k-vector spaces Ω_{X,P} ⊗_{O_{X,P}} κ(P) and 𝔪_{P} /𝔪_{P}^{2} are canonically isomorphic; see [Har77, II, Proposition 8.7]. Either one of these spaces is called the cotangent space at P. The Zariski tangent space or simply tangent space of P in X is T_{P} (X) := Hom_{k}(𝔪_{P} /𝔪_{P}^{2} , k). The formation of the tangent spaces behaves well under base change via a field extension over k. Let us note here that it is important that P is a k-rational point. A special case which is of importance in this work is: For any finite dimensional k-vector space V we have a canonical isomorphism T_{0}(𝔸_{k}[V]) ≃ V; we identify these spaces.

Let now X be a smooth k-scheme. Then the tangent sheaf of X is T_{X} := Ω_{X}^{∨} = Hom_{O_{X}} (Ω_{X}, O_{X}). The canonical homomorphism

T_{X,P} ≃ Hom_{O_{X,P}} (Ω_{X,P} , O_{X,P}) ⟶ Hom_{O_{X,P}} (Ω_{X,P} , κ(P))
≃ Hom_{k}(Ω_{X,P} ⊗_{O_{X,P}} κ(P), k) ≃ T_{P} (X)

induces a homomorphism of k-vector spaces

T_{X,P} ⊗_{O_{X,P}} κ(P) ⟶ T_{P} (X) .

As Ω_{X,P} is (by assumption) a free O_{X,P} -module, this homomorphism is an isomorphism. We denote the image of t ∈ T_{X,P} in T_{P} (X) by t(P).

Now let X and Y be arbitrary k-schemes of finite type, let f : X ⟶ Y be a morphism of k-schemes and let P ∈ X. Then the local ring of P in its fiber over f(P) is O_{X,P} /f^{#}(𝔪_{Y,f(P)})O_{X,P}, and f is said to be unramified at P if this local ring is a finite and separable κ(f(P))-algebra. If f is unramified at P then it is in particular quasi-finite at P, that is, P is isolated in its fiber.

Let now P be a k-rational point of X. Then f is unramified at P if and only if f^{#}(𝔪_{Y,f(P)}) generates the maximal ideal of O_{X,P}. By Nakayama’s lemma, this is the case if and only if the induced homomorphism between cotangent spaces f^{∗} : 𝔪_{f(P)}/𝔪_{f(P)}^{2} ⟶ 𝔪_{P} /𝔪_{P}^{2} is surjective. Therefore, f is unramified at P if and only if the induced homomorphism between tangent spaces f_{∗} : T_{P} (X) ⟶ T_{f(P)}(Y) is injective.

Acknowledgment

I thank the anonymous referee for carefully reading this work and for suggestions. I thank Tian Song for pointing out the misprints in [Die11b] I mention in the appendix.

2 The factor base

2.1 Some general thoughts

In [Die11b] we first described the algorithm, which is rather elementary, and later presented the geometric background, involving in particular the role of the Weil restriction of the elliptic curve with respect to 𝔽_{q^{n}}|𝔽_{q}.

This approach would also be possible here. However, we now present the geometric background together with the description of the algorithm. The main reason for this is that the conditions required for the definition of the factor base are quite involved but closely related to geometric considerations.

We first make some remarks on the definition of the factor base in [Die11b].

Let an instance with a non-trivial extension of finite fields 𝔽_{q^{n}}|𝔽_{q} and an elliptic curve E over 𝔽_{q^{n}} be given, where an affine part of E is given by a Weierstraß equation in x and y with degree 2 in x. Let k := 𝔽_{q} and K := 𝔽_{q^{n}}.

Then in [Die11b], the factor base is defined as follows:

We fix a covering φ : E ⟶ ℙ_{K}^{1} of degree 2 with φ ∘ [−1] = φ satisfying a certain condition (Condition 2.7 in [Die11b]). Then the factor base F is the set

{P ∈ E(K) | φ(P) ∈ ℙ^{1}(k)} .  (2)

Now there exists a unique automorphism α of ℙ_{k}^{1} with φ = α ∘ x_{|E}. The factor base is then equal to

{P ∈ E(K) | x_{|E}(P) ∈ α^{−1}(ℙ^{1}(k))} .  (3)

A geometric description of the definition of the factor base in (2) is as follows: Let ι = id_{⊚} : ℙ_{k}^{1} ⟶ Res_{k}^{K}(ℙ_{k}^{1}) be the morphism corresponding to the identity on ℙ_{K}^{1} under the universal property of the Weil restriction. This morphism is a closed immersion, it might be called the canonical immersion.

We define V by the diagram

\xymatrix{V \ar@{^{(}->}[r] \ar[d] & Res_{k}^{K}(E) \ar[d]^{Res_{k}^{K}(φ)} \\ ℙ_{k}^{1} \ar@{^{(}->}[r]^{ι} & Res_{k}^{K}(ℙ_{k}^{1})}  (4)

being Cartesian; cf. subsection 4.3 of [Die11b]. Then under the canonical isomorphism E(K) ≃ Res_{k}^{K}(E)(k), the factor base F corresponds to V (k). Recall here that as the morphism φ : E ⟶ ℙ_{K}^{1} is a flat covering of degree 2, the morphism Res_{k}^{K}(φ) : Res_{k}^{K}(E) ⟶ Res_{k}^{K}(ℙ_{K}^{1}) and the induced morphism V ⟶ ℙ_{k}^{1} are flat coverings of degree 2^{n}.

From a geometric point of view, the equivalence of the two descriptions of the factor base via (2) and (3) follows from the commutativity of the diagram

[figure: V; Res_{k}^{K}(E); Res_{k}^{K}(x_{|E}); Res_{k}^{K}(φ); ℙ_{k}^{1}; (α^{−1})_{⊚}; ι; Res_{k}^{K}(ℙ_{K}^{1}); Res_{k}^{K}(α); Res_{k}^{K}(ℙ_{K}^{1}) .]

Note here that by the universal property of the Weil restriction of ℙ_{K}^{1} with respect to K|k, the immersions ℙ_{k}^{1} ↪ Res_{k}^{K}(ℙ_{K}^{1}) correspond exactly to the automorphisms of ℙ_{K}^{1} (via α ↦ α_{⊚}). Thus instead of varying the covering φ : E ⟶ P_{K}^{1} in the construction of the factor base, we could also have varied the immersion of ℙ_{k}^{1} into Res_{k}^{K}(ℙ_{K}^{1}).

2.2 The preliminary definition of the factor base

We now give some geometric background on the definition of the factor base in the preliminary algorithm outlined in the introduction. We conclude this subsection with a wish list on the geometric objects related to the definition of the factor base. This then leads to a modification of the construction of the factor base which is described in the next subsection.

Let E_{a} be the “affine part” of E, that is, E_{a} := x_{|E}^{−1}(𝔸_{K}^{1}). Furthermore, as already mentioned above, let m be some natural number at most n and let d := ⌈\frac{n}{m}⌉ and δ := dm − n.

In the preliminary algorithm in the introduction we defined the factor base as follows: We fix a d-dimensional k-vector subspace U of K, and we set

F := {P ∈ E_{a}(K) | x(P) ∈ U} .

We now give a geometric description. As mentioned in the introduction, the inclusion U ↪ K gives rise to a closed immersion 𝔸_{k}[U] ⟶ 𝔸_{k}[K], and thus 𝔸_{k}[U] is a group subvariety of 𝔸_{k}[K] = Res_{k}^{K}(𝔸_{K}^{1}). Defining V_{a} ⊆ Res_{k}^{K}(E) by the diagram

\xymatrix{V_{a} \ar@{^{(}->}[r] \ar[d] & Res_{k}^{K}(E_{a}) \ar[d] \ar[d]^{Res_{k}^{K}(x_{|Ea})} \\ 𝔸_{k}[U] \ar@{^{(}->}[r] & 𝔸_{k}[K] ,}  (5)

being Cartesian, the factor base corresponds to V_{a}(k).

In the preliminary algorithm, we also have a (d−1)-dimensional k-vector subspace U′ of U, defining a subset F′ of F. We define V′_{a} analogously to V_{a} with 𝔸_{k}[U] being substituted by 𝔸_{k}[U′]. Then F′ corresponds to V′_{a}(k). As the maps V_{a} ⟶ A and V′_{a} ⟶ A′ are finite flat, every irreducible component of V_{a} has dimension m and every irreducible component of V′_{a} has dimension m − 1; see [Har77, III, Corollary 9.6].

Now, we would like that the following conditions on V_{a} and V′_{a} are satisfied:

1. The addition morphism (Res_{k}^{K}(E))^{m} ⟶ Res_{k}^{K}(E) induces a dominant morphism from every irreducible component of (V′_{a})^{δ}×V_{a}^{m−δ} to Res_{k}^{K}(E).

2. There exists an (absolute) constant c > 0 such that V_{a}(k) contains at least c · q^{d} points and V′_{a}(k) contains at least c · q^{d−1} points.

Note that dim((V′_{a})^{δ} × V_{a}^{m−δ}) = n and therefore the statement in the first item implies that the morphism (V′_{a})^{δ} × V_{a}^{m−δ} ⟶ Res_{k}^{K}(E) is generically finite.

With a randomized algorithm it is straightforward to construct in an efficient way U and U′ such that the second item is satisfied.

For d = 1, the morphism (V′_{a})^{δ} × V_{a}^{m−δ} ⟶ Res_{k}^{K}(E) is surjective and therefore if V′_{a} and V_{a} are irreducible, the first item is satisfied; see [Die11b, Remark 4.21]. However, for d > 1, we cannot even give an example for which we can prove that the first condition holds. For this reason, we modify the definition of the factor base.

2.3 The essential modification

We now discuss the modification of the construction of the factor base. We impose the following condition.

Condition 2.1 The point 0 ∈ ℙ_{K}^{1} is not a branch point of x_{|E} : E ⟶ ℙ_{K}^{1} and its preimage in E consists of two K-rational points.

Note that for q^{n} ≥ 16, there exist at least 5 K-rational points on E, so there exists a point in E(K) which is not a ramification point. In the algorithm for the definition of the factor base, we first pass to a projectively equivalent elliptic curve, also given in Weierstraß form with the point at infinity being the neutral element, such that the condition is satisfied. We then fix k-vector subspaces U_{i} of K of dimension d − 1 for i = 1, …, δ and of dimension d for i = δ + 1, …, m such that we have a decomposition

K = ⨁_{i=1}^{m} U_{i}  (6)

and such that some further conditions are satisfied; cf. subsection 2.5 below. With

F_{i} := {P ∈ E_{a}(K) | x(P) ∈ U_{i} − {0}} ,  (7)

we define the factor base as

F := ⋃_{i=1}^{m} F_{i} .  (8)

Later, for P ∈ E(K), we search for a relation of the form

P_{1} + ⋯ + P_{m} = P

with P_{i} ∈ F_{i}.

We now apply the geometric considerations of the previous subsection here. Decomposition (6) gives rise to a decomposition

𝔸_{k}[K] = ⨁_{i=1}^{m} 𝔸_{k}[U_{i}]  (9)

in the category of commutative k-group varieties. Decomposition (6) is then obtained from (9) by taking k-valued points.

Similarly to above, we define V_{i} ⊆ Res_{k}^{K}(E_{a}) via the diagram

\xymatrix{V_{i} \ar@{^{(}->}[r] \ar[d] & Res_{k}^{K}(E_{a}) \ar[d] \\ 𝔸_{k}[U_{i}] \ar@{^{(}->}[r] & 𝔸_{k}[K]}

being Cartesian. Note that the morphism Res_{k}^{K}(E_{a}) ⟶ 𝔸_{k}[K] is a flat covering of degree 2^{n} which is unramified at 0 ∈ 𝔸_{k}[K]. As flatness and unramifiedness are stable under base change, the morphism V_{i} ⟶ 𝔸_{k}[U_{i}] is a flat covering of degree 2^{n} which is unramified at 0 ∈ 𝔸_{k}[U_{i}] too. In particular, V_{i} has the same dimension as the vector space U_{i}.

Let

a_{m} : Res_{k}^{K}(E)^{m} ⟶ Res_{k}^{K}(E)  (10)

be the m-fold addition morphism and

a′_{m} : V_{1} × ⋯ × V_{m} ⟶ Res_{k}^{K}(E)  (11)

be the restriction of a_{m} to V_{1} × ⋯ × V_{m}. Let P_{0} be one of the two points of E(K) which are mapped to 0 by x_{|E}.

Note that Res_{k}^{K}((P_{0})_{⊚}) = 0. In particular, (P_{0})_{⊚} is a k-rational point of all V_{i}.

Proposition 2.2 The morphism a′_{m} is unramified at ((P_{0})_{⊚}, …, (P_{0})_{⊚}).

Remark 2.3 As unramifiedness is an open property, we obtain: a′_{m} is unramified in an open neighborhood of ((P_{0})_{⊚}, …, (P_{0})_{⊚}). Every irreducible component of V_{1} × ⋯ × V_{m} has dimension n (because we have a flat covering of V_{1} × ⋯ × V_{m} to 𝔸_{k}[K]). Thus the morphism a′_{m} is dominant. If furthermore V_{1}, …, V_{m} are irreducible, a′_{m} is generically unramified.

Proof of Proposition 2.2. We wish to show that

(a′_{m})_{∗} : T_{((P_{0})_{⊚},...,(P_{0})_{⊚})}(V_{1} × ⋯ × V_{m}) ⟶ T_{m·(P_{0})_{⊚}}(Res_{k}^{K}(E))

is an isomorphism.

As the morphism Res_{k}^{K}(x_{|E}) is unramified at (P_{0})_{⊚}, it induces an isomorphism of tangent spaces

T_{(P_{0})_{⊚}}(Res_{k}^{K}(E_{a})) ⟶^{∼} T_{0}(𝔸_{k}[K]) .  (12)

Decomposition (9) induces a decomposition of tangent spaces T_{0}(𝔸_{k}[K]) = ⨁_{i=1}^{m} T_{0}(𝔸_{k}[U_{i}]) which is nothing but the original decomposition of vector spaces K = ⨁_{i=1}^{m} U_{i}. Under isomorphism (12), T_{(P_{0})_{⊚}}(V_{i}) corresponds to T_{0}(𝔸_{k}[U_{i}]). Therefore, we have the decomposition

T_{(P_{0})_{⊚}}(Res_{k}^{K}(E_{a})) = ⨁_{i=1}^{m} T_{(P_{0})_{⊚}}(V_{i}) .  (13)

By the next lemma, we have the commutative diagram whose vertical maps are isomorphisms

\xymatrix{T_{((P_{0})_{⊚},...,(P_{0})_{⊚})}(Res_{k}^{K}(E)^{m}) \ar[d]_{((p_{1})_{∗},...,(p_{m})_{∗})} \ar[r]^{(a_{m})_{∗}} & T_{m(P_{0})_{⊚}}(Res_{k}^{K}(E)) \\ (T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)))^{m} \ar[r]^{∑} & T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)) . \ar[u]_{(τ_{(m−1)·(P_{0})_{⊚}})_{∗}}}

Here p_{i} : Res_{k}^{K}(E)^{m} ⟶ Res_{k}^{K}(E) is the projection to the i^{th} coordinate and the map ∑ : T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)) ⟶ T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)) is the addition of the k-vector space T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)).

By restriction of the horizontal maps we obtain the commutative diagram

\xymatrix{T_{((P_{0})_{⊚},...,(P_{0})_{⊚})}(V_{1} × ⋯ × V_{m}) \ar[r]^{(a_{m})_{∗}} \ar[d] & T_{m(P_{0})_{⊚}}(Res_{k}^{K}(E)) \\ T_{(P_{0})_{⊚}}(V_{1}) × ⋯ × T_{(P_{0})_{⊚}}(V_{m}) \ar[r]^{∑} & T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)) . \ar[u]_{(τ_{(m−1)·(P_{0})_{⊚}})_{∗}}}

Now because of decomposition (13), under the addition, T_{(P_{0})_{⊚}}(V_{1})×⋯×T_{(P_{0})_{⊚}}(V_{m}) is mapped bijectively to T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)). This gives the desired statement. □

In the following lemma, we use this notation: Let U, V, W be k-vector spaces. If then φ : U ⟶ W and ψ : V ⟶ W are k-linear maps, we denote the induced map U × V ⟶ W by ( φ ψ ). If φ : W ⟶ U and ψ : W ⟶ V are k-linear maps, we denote the induced map W ⟶ U × V

by ( \begin{matrix}φ \\ ψ \end{matrix} ).

Lemma 2.4 Let k be a field.

a) Let X_{1}, X_{2} be two k-schemes, and let P_{1} ∈ X_{1}(k), P_{2} ∈ X_{2}(k). Let us assume that X_{1} is smooth at P_{1} and X_{2} is smooth at P_{2}. The points P_{i} give rise to closed immersions ι_{i} : X_{i} ⟶ X_{1} × X_{2}. Let p_{i} : X_{1} × X_{2} ⟶ X_{i} be the canonical projections. Then the maps ( (ι_{1})_{∗} (ι_{2})_{∗} ) : T_{P_{1}}(X_{1}) × T_{P_{2}}(X_{2}) ⟶ T_{(P_{1},P_{2})}(X_{1} × X_{2}) and

( \begin{matrix}(p_{1})_{∗} \\ (p_{2})_{∗} \end{matrix} ) : T_{(P_{1},P_{2})}(X_{1} × X_{2}) ⟶ T_{P_{1}}(X_{1}) × T_{P_{2}}(X_{2}) are isomorphisms

of k-vector spaces which are inverse with respect to each other.

b) Let A be an abelian variety over k with addition morphism a : A×A ⟶ A and neutral element O. Let ι_{i} : A ⟶ A × A be the two canonical immersions. Then the map a_{∗} ∘ ( (ι_{1})_{∗} (ι_{2})_{∗} ) : T_{O}(A) × T_{O}(A) ⟶ T_{O}(A) is the addition on the k-vector space T_{O}(A).

c) Let A be an abelian variety over k and P ∈ A(k). Then we have a commutative diagram

\xymatrix{ & T_{P} (A × A) \ar[r]^{a_{∗}} & T_{2P} (A) \\ _{( \begin{matrix}(p_{1})_{∗} \\ (p_{2})_{∗} \end{matrix} )} \ar[dr] \\  & T_{P} (A) × T_{P} (A) \ar[r]^{∑} & T_{P} (A) , \ar[uu]_{(τ_{P})_{∗}}}

where the lower map ∑ : T_{P} (A) × T_{P} (A) ⟶ T_{P} (A) is the addition morphism on the k-vector space T_{P} (A).

Proof. a) The k-linear map

[figure: T_{P_{1}}(X_{1}) × T_{P_{2}}(X_{2}); ( (ι_{1})_{∗} (ι_{2})_{∗} ); T_{(P_{1},P_{2})}(X_{1} × X_{2}); ^{( \begin{matrix}(p_{1})_{∗} \\ (p_{2})_{∗} \end{matrix} )}; T_{P_{1}}(X_{1}) × T_{P_{2}}(X_{2})]

is obviously the identity. As the dimensions of these k-vector spaces are the same, the two maps in a) are both isomorphisms.

b) We only have to check that the k-linear map a_{∗} ∘ ( (ι_{1})_{∗} (ι_{2})_{∗} ) : T_{O}(A) × T_{O}(A) ⟶ T_{O}(A) agrees with the addition (which is also k-linear) on the first and second factor. But restricted to factor i, a_{∗} ∘( (ι_{1})_{∗} (ι_{2})_{∗} ) becomes a_{∗}∘(ι_{i})_{∗}, which is the identity, just as is the addition when restricted to one of the factors.

c) Let us consider A as an abelian variety with P as neutral element, and let a_{P} be the addition law. Then a_{P} = τ_{−P} ∘ a. The commutativity of the diagram then follows from b). □

2.4 Irreducibility

If the characteristic is odd, in order to complete the analysis of the relation generation procedure, we need that the V_{i} are irreducible. In this subsection, we give some theoretical background for the algorithmic construction of the V_{i} such that they are indeed irreducible.

All the statements in this subsection are valid except in the case that the characteristic is 2 and the j-invariant of E is 0, or, in other words, except if E is a supersingular elliptic curve in characteristic 2. So let us assume that it does not hold that the characteristic is 2 and j = 0.

Lemma 2.5 Let U be a vector subspace of K, and let V_{a} be defined as in (5). If 𝔸_{k}[U] contains an irreducible scheme containing 0 whose preimage in V_{a} is irreducible, then V_{a} is irreducible. Likewise, if 𝔸_{k}[U] contains a geometrically irreducible scheme containing 0 whose preimage in V_{a} is geometrically irreducible, then V_{a} is geometrically irreducible.

Proof. Assume that V_{a} is not irreducible, and let V_{a}^{(1)} and V_{a}^{(2)} be two irreducible components of V_{a}. Let A ⊆ 𝔸_{k}[U] be the étale locus of the flat covering V_{a} ⟶ 𝔸_{k}[U] and V_{a} its preimage on V_{a}. By Condition 2.1 the covering E_{a} ⟶ 𝔸_{K}^{1} is unramified at 0. Thus so is the covering Res_{k}^{K}(E_{a}) ⟶ 𝔸_{k}[K] and the induced covering V_{a} ⟶ 𝔸_{k}[U]. Thus 0 is contained in A. In particular, A is non-empty and thus a non-empty open part of 𝔸_{k}[U].

For i = 1, 2, the map V_{a}^{(i)} ⟶ 𝔸_{k}[U] is surjective. (As the map V_{a}^{(i)} ⟶ 𝔸_{k}[U] is flat and finite, by [Har77, Chapter III, Corollary 9.6], V_{a}^{(i)} has the same dimension as 𝔸_{k}[U]. The dimension of V_{a}^{(i)} is equal to the dimension of its image. Thus the dimension of the image is equal to 𝔸_{k}[U]. Therefore the map is dominant. As the map is finite, it is in particular closed, and therefore the image is equal to 𝔸_{k}[U].) Therefore V_{a}^{(i)} contains a preimage of 0. Let V_{a}^{(i)} be the preimage of A in V_{a}^{(i)}. Then V_{a}^{(i)} is a non-empty open part of V_{a}^{(i)} which contains a preimage of 0.

As 𝔸_{k}[U] is smooth so is A, and as furthermore V ⟶ A is étale, V is also smooth. It follows that V_{a}^{(1)} and V_{a}^{(2)} are disjoint.

Let now S be an irreducible subscheme of 𝔸_{k}[U] as in the first claim of the lemma. As V_{a} ⟶ 𝔸_{k}[U] is unramified at 0 and 0 ∈ S by assumption, S ∩ A is a non-empty open part of S. It follows that the preimage of S ∩ A is a non-empty open part of the preimage of S and thus also irreducible. Therefore it is contained in either V_{a}^{(1)} or V_{a}^{(2)}. On the other hand, as it contains all preimages of 0, it has non-trivial intersection with both V_{a}^{(1)} and V_{a}^{(2)}, a contradiction.

The second claim follows via base change to \overline{k}. □

In the algorithm, we first search for 1-dimensional k-vector subspaces T_{i} of K such that the preimages of 𝔸_{k}[T_{i}] in Res_{k}^{K}(E_{a}) with respect to Res_{k}^{K}(x_{|E_{a}}) are geometrically irreducible. Then we search for suitable kvector subspaces U_{i} of K containing T_{i}. The preimages V_{i} of the corresponding group subvarieties 𝔸_{k}[U_{i}] of 𝔸_{k}[K] then contain 𝔸_{k}[T_{i}] and are therefore geometrically irreducible.

To choose the spaces T_{i} we employ ideas from the first subsection of this section and of our previous work.

Let μ ∈ K^{∗}, and let us consider the vector subspace μ^{−1} · k of K and the associated group subvariety 𝔸[μ^{−1} · k] of 𝔸_{k}[K]. Furthermore, let W_{a} be the preimage of 𝔸[μ^{−1} · k] in Res_{k}^{K}(E_{a}).

Clearly, the group subvariety 𝔸[μ^{−1} · k] is the image under the closed immersion 𝔸_{k}^{1} ⟶ 𝔸_{k}[K] induced by the injective homomorphism of vector spaces k ⟶ K , a ↦ μ^{−1}a. This morphism can also be given as follows: Let α_{a} := μx : 𝔸_{k}^{1} ⟶ 𝔸_{k}^{1}. Then the morphism 𝔸_{k}^{1} ⟶ 𝔸_{k}[K] is equal to (α_{a}^{−1})_{⊚}.

We now essentially apply the considerations of subsection 2.1 here, restricting ourselves to the “affine parts”. We set φ_{a} := α_{a} ∘ x_{|E_{a}}. Now W_{a} is the preimage of ι(𝔸_{k}^{1}) in Res_{k}^{K}(E_{a}) with respect to the covering Res_{k}^{K}(φ_{a}). This is very closely related to the situation studied in [Die11b, Section 2.2]

– the only difference is that here we use automorphisms of the group variety 𝔸_{K}^{1} instead of automorphisms of ℙ_{K}^{1} and we restrict ourselves to the “affine parts”.

Lemma 2.6 There are more than q^{n} − 3(n − 1) · q^{n/2} elements μ ∈ K^{∗} such that, with W_{a} as defined as above, W_{a} is geometrically irreducible.

Proof. By assumption on k and E, the covering x_{|E} : E\overline{k} ⟶ ℙ1 ; \overline{k} has two or four branch points, one of which is at infinity. Thus there are exactly one or three branch points not equal to infinity.

Let λ_{1}, …, λ_{s} ∈ 𝔽_{q^{6n}} − {0} with s ∈ {1, 3} be the branch points of x_{|E_{a}} : (E_{a})\overline{k} ⟶ 𝔸1 ; \overline{k}. Let μ ∈ K^{∗} and let α := μx. Then the branch points of α ∘ x_{|E_{a}} : (E_{a})\overline{k} ⟶ 𝔸1 ; \overline{k} are μλ_{1}, …, μλ_{s}. Therefore Condition 2.7 from [Die11b] is equivalent to the following condition.

Condition 2.7 There exists an i = 1, …, s such that for j = 1, …, n − 1, (μλ_{i})^{q^{j}} ∉ {μλ_{1}, …, μλ_{s}}.

As shown in [Die11b, Proposition 4.9], if this condition is satisfied, W_{a} is geometrically irreducible.

We are interested in the probability that for j = 1, …, n − 1, (μλ_{1})^{q^{j}} ∉ {μλ_{1}, …, μλ_{s}}.

For j = 1, …, n − 1 and ℓ = 1, …, s, the condition (μλ_{1})^{q^{j}} = μλ_{ℓ} is equivalent to μ^{q^{j}−1} = _{\frac{λ_{ℓ}}{λ_{1}^{q^{j}}}}. As the cardinality of the kernel of the map

K^{∗} ⟶ \overline{k}^{∗} , a ↦ a^{q^{j}−1} is q^{gcd(j,n)} − 1 (see next lemma), there are either no or exactly q^{gcd(j,n)} − 1 such elements μ.

The situation is now very similar to the situation in [Die11b, Lemma 2.10]: In total there are at most s · ∑_{j=1}^{n−1}(q^{gcd(j,n)} − 1) elements μ for which the condition in the lemma is not satisfied.

Now a crude estimate is that s · ∑_{j=1}^{n−1} q^{gcd(j,n)−1} < s · (n − 1) · q^{n/2}. □

Lemma 2.8 Let q be a prime power and m, n ∈ ℕ. Then q^{m} − 1 | q^{n} − 1 if and only if m | n. Moreover gcd(q^{m} − 1, q^{n} − 1) = q^{gcd(m,n)} − 1.

Proof. If m | n then clearly q^{m} − 1 | q^{n} − 1. So assume that q^{m} − 1 | q^{n} − 1. For a ∈ 𝔽_{q^{m}}^{∗} we have a^{q^{m}−1} = 1 and by assumption also a^{q^{n}−1} = 1. But this means that a ∈ 𝔽_{q^{n}}^{∗}. Thus 𝔽_{q^{m}} is a subfield of 𝔽_{q^{n}} and thus m|n.

For the second statement, consider the set G := {a ∈ 𝔽_{q^{n}} | a^{q^{m−1}} = 1}. On the one hand, as G is a subgroup of the cyclic group 𝔽_{q^{m}}^{∗}, it has gcd(q^{m} − 1, q^{n} − 1) elements. On the other hand, G ∪ {0} is a subfield of 𝔽_{q^{n}}, and therefore there exists some a|n with #G = q^{a} − 1 . The result now follows with the first statement. □

2.5 The algorithm for the factor base

Let a field extension K|k as above, an elliptic curve E/K, two points A, B ∈ E(K) with B ∈ ⟨A⟩ as well as m ∈ ℕ with 2 ≤ m ≤ n be given, where #K ≥ 16. As always, let d := ⌈\frac{n}{m}⌉ and δ := dm − n.

We first choose – with a randomized algorithm – some point P_{0} ∈ E_{a}(K) which is not a ramification point of x_{|E} and pass from E to its image under the automorphism of ℙ_{K}^{2} given by P = (X(P) : Y (P) : Z(P)) ↦ (X(P) − x(P_{0})Z(P) : Y (P) : Z(P)). Let Ẽ be the resulting curve. This is again a curve in Weierstraß form, x_{|Ẽ} is unramified above 0 and the preimage of 0 consists of two K-rational points. Clearly, this computation can be performed in an expected time which is polynomially bounded in log(q^{n}).

So let us now assume that there exists a K-rational point of E which is unramified under x_{|E} and mapped to 0.

Given an instance as described, we wish to compute a decomposition K = ⨁_{i=1}^{m} U_{i} with dim(U_{i}) = d − 1 for i = 1, …, δ and dim(U_{i}) = d for i = δ + 1, …, m such that

• #\{P ∈ E_{a}(K) | x(P) ∈ U_{i} − \{0\}\} ≥ \frac{1}{4}q^{dim(U_{i})};

• if char(k) is odd: V_{1}, …, V_{m} are irreducible.

The factor base is then defined as described in Equations (7) and (8) above.

We now give an algorithm for the task just mentioned under the condition that m ≤ \frac{n}{2} and q ≥ 4. This is sufficient for the algorithm for Theorem 2.

Algorithm to compute a suitable decomposition of K

Input: A field extension 𝔽_{q^{n}}|𝔽_{q} with q ≥ 4, an elliptic curve E/𝔽_{q^{n}} in Weierstraß form with respect to x and y such that there is a K-rational point of E which is unramified under x_{|E} and mapped to 0, two points A, B ∈ E(𝔽_{q^{n}}) with B ∈ ⟨A⟩ and a natural number m with 2 ≤ m ≤ \frac{n}{2}.

Output: A decomposition 𝔽_{q^{n}} = ⨁_{i=1}^{m} U_{i} with dim(U_{i}) = d − 1 for i = 1, …, δ and dim(U_{i}) = d for i = δ + 1, …, m such that the conditions mentioned above are satisfied.

1. If q is not a power of 2

For i = 1, …, m do Repeat

Choose μ_{i} ∈ 𝔽_{q^{n}}^{∗} uniformly at random. Until μ_{i} is not contained in ⟨T_{1}, …, T_{i−1}⟩ and μ_{i} satisfies Condition 2.7. Let T_{i} ⟵ μ_{i}^{−1} · 𝔽_{q} < 𝔽_{q^{n}}.

If q is a power of 2, let T_{i} ⟵ {0} for i = 1, …, m.

2. Let d ⟵ ⌈\frac{n}{m}⌉ and δ ⟵ dm − n.

For i = 1, …, m do If i ≤ δ, let e ⟵ d − 1, otherwise let e ⟵ d. Repeat

Compute an 𝔽_{q}-vector subspace U_{i} of 𝔽_{q^{n}} which is uniformly randomly chosen from the set of e-dimensional 𝔽_{q}-vector subspaces of 𝔽_{q^{n}} containing T_{i} with intersection {0} with U_{1} + ⋯ + U_{i−1} + T_{i+1} + ⋯ + T_{m}.

Until \{E_{a}(𝔽_{q^{n}}) | x(P) ∈ U_{i} − \{0\}\} contains at least \frac{1}{4} · q^{e} elements.

3. Output U_{1}, …, U_{m}.

Remark 2.9 We represent 𝔽_{q}-vector subspaces of 𝔽_{q^{n}} by bases over 𝔽_{q}. Therefore the definition of T_{i} is computationally void; we inserted it only to be able to reason about T_{i} later.

Note here that at the end of each iteration of the For-loop in Step 2, we have a direct sum U_{1} ⊕ ⋯ ⊕ U_{i} ⊕ T_{i+1} ⊕ ⋯ ⊕ T_{m} inside K, where for j = 1, …, i, U_{j} contains T_{j}, dim(U_{j}) = d − 1 if j ≤ δ and dim(U_{j}) = d if j > δ. The vector space T_{i} corresponds to a 1-dimensional group subscheme of 𝔸_{k}[K] whose preimage in Res_{k}^{K}(E) is geometrically irreducible by the arguments in Lemma 2.6. By Lemma 2.5, V_{i} is then also geometrically irreducible. Therefore an output of the algorithm defines a decomposition K = ⨁_{i=1}^{m} U_{i} which satisfies the conditions given above.

We remark here that the algorithm itself is much more elementary than the geometric arguments.

The main result of this section is the following proposition.

Proposition 2.10 For 2 ≤ m ≤ \frac{n}{2} and q ≥ 4, following the above algorithm, one can compute a decomposition of K with the desired properties in an expected time of Poly(n · q^{d}) = Poly(n · q^{\frac{n}{m}}).

Proof. We only have to consider the expected running time. For this, we discuss the steps of the algorithm.

\underline{Step 1} Let q be odd. We consider, for a particular iteration of the For-loop, the expected value of iterations of the Repeat-loop.

As i ≤ m, the space ⟨T_{1}, …, T_{i−1}⟩ contains at most q^{m−1} ≤ q^{n/2} elements. By Lemma 2.6, there are at least q^{n} − 3(n − 1) · q^{n/2} − q^{n/2} ≥ q^{n} − 3n · q^{n/2} elements μ ∈ K^{∗} which do not lie in ⟨T_{1}, …, T_{i−1}⟩ and which satisfy Condition 2.7. The probability that this is satisfied is therefore at least 1 − 3n · \frac{1}{q^{n/2}} . For n ≥ 4 and q ≥ 4, which is the case by assumption, this is at least 1 − \frac{3n}{2^{n}} ≥ 1 − \frac{12}{16} = \frac{1}{4}. The expected value of iterations of the Repeat-loop is therefore at most 4. We can obtain an expected running time which is polynomially bounded in n · log(q).

\underline{Step 2} We always have e ≥ 2. In the Repeat loop, the space U_{i} can be computed in an expected time which is polynomially bounded in n · log(q) by the next lemma. The counting of the set {E_{a}(𝔽_{q^{n}}) | x(P) ∈ U_{i} −{0}} can be performed in a time which is polynomially bounded in q^{d}. The expected number of repetitions of the loop is at most 14 by Lemma 2.12 below. The expected running time of Step 2 is then polynomially bounded in q^{d}. □

Lemma 2.11 Let S and T be two 𝔽_{q}-vector subspaces of 𝔽_{q}^{n} with S∩T = {0} and S + T ⊊ 𝔽_{q}^{n}, and let e ∈ ℕ with dim(T) ≤ e ≤ n − dim(S) be given. Then in an expected time which is polynomially bounded in n·log(q) one can compute an 𝔽_{q}-vector subspace U of 𝔽_{q}^{n} which is uniformly randomly chosen from the set of e-dimensional 𝔽_{q}-vector subspaces U of 𝔽_{q} with T ⊆ U and S ∩ U = {0}.

Proof. Consider the following algorithm:

Input: Two 𝔽_{q}-vector subspaces S and T of 𝔽_{q}^{n} with S ∩ T = {0}, and e ∈ ℕ with dim(T) ≤ e ≤ n − dim(S).

Output: An 𝔽_{q}-vector subspace U satisfying the conditions given in the lemma.

Let v_{1}, …, v_{dim(T)} be the basis of T given with the input.

For i = dim(T) + 1, …, e do

Repeat

Choose v_{i} ∈ 𝔽_{q}^{n} uniformly at random. Until v_{i} ∉ ⟨v_{1}, …, v_{i−1}⟩ + S.

Output ⟨v_{1}, …, v_{e}⟩.

Obviously the space ⟨v_{1}, …, v_{e}⟩ is uniformly randomly distributed in the set of e-dimensional subspaces U of 𝔽_{q}^{n} with T ⊆ U and S ∩ U = {0}.

The claimed expected running time follows easily from the fact that the probability that v_{i} is in the (i − 1 + dim(S))-dimensional vector subspace is q^{(i−1)+dim(S)−n} ≤ \frac{1}{q}. □

Lemma 2.12 For q ≥ 4 and n ≥ 4, elliptic curves E/𝔽_{q^{n}} in Weierstraß form, proper 𝔽_{q}-vector subspaces S and T of 𝔽_{q^{n}} with dim(S) ≤ n − 2, S ∩ T = {0} and S + T ⊊ 𝔽_{q}^{n} and a natural number e with dim(T) < e ≤ n − dim(S), the following holds:

Let U be a uniformly randomly distributed vector subspace of 𝔽_{q}^{n} of dimension e with T ⊆ U and S ∩ U = {0}. Then with a probability of at least \frac{1}{14}, #\{P ∈ E_{a}(𝔽_{q^{n}}) | x(P) ∈ U − \{0\}\} ≥ \frac{1}{4} · q^{e}.

Proof. Let first U be a uniformly randomly distributed e-dimensional 𝔽_{q}-vector subspace of 𝔽_{q^{n}}. Then as each point of 𝔽_{q^{n}} − {0} has the same probability of appearing in U, each point of 𝔽_{q^{n}} − {0} has a probability of

\frac{q^{e} − 1}{q^{n} − 1}

to appear in U.

Likewise, if S, T and e are as in the lemma and U is a uniformly randomly distributed e-dimensional vector subspace of 𝔽_{q^{n}} with T ⊆ U and U ∩ S = {0}, each point of 𝔽_{q^{n}} − (S ∩ T) has a probability of

\frac{q^{e} − q^{dim(T)}}{q^{n} − q^{dim(S)}} ≥ \frac{1}{2} · q^{e−n}

to appear in U.

Let

S := {P ∈ E_{a}(𝔽_{q^{n}}) | x(P) ∈ S} ,
T := {P ∈ E_{a}(𝔽_{q^{n}}) | x(P) ∈ T − {0}} ,
N := #{P ∈ E_{a}(𝔽_{q^{n}}) | x(P) ∈ U − {0}} .

The expected value of N, 𝔼[N], can be expressed as follows:

𝔼[N] = #(E_{a}(𝔽_{q^{n}}) − (S ∪ T )) · \frac{q^{e} − q^{dim(T)}}{q^{n} − q^{dim(S)}} + #T

≥ (#E_{a}(𝔽_{q^{n}}) − #S) · \frac{q^{e} − q^{dim(T)}}{q^{n} − q^{dim(S)}}

≥ (q^{n} − 2 · q^{n/2} − 2 · q^{dim(S)}) · \frac{1}{2} · q^{e−n} ,

the last inequality by the Hasse-Weil bound.

As q ≥ 4 and n ≥ 4, 2 · q^{n/2} ≤ \frac{1}{8} · q^{n}. As q ≥ 4 and dim(S) ≤ n − 2, 2 · q^{dim(S)} ≤ 2 · q^{n−2} ≤ \frac{1}{8} · q^{n}. We obtain:

𝔼[N] ≥ \frac{3}{8} · q^{e}

On the other hand, N ≤ 2 · q^{e}. The claimed bound on the probability that N ≥ \frac{1}{4} · q^{e} now follows by the following elementary probability theoretic argument. We have

\frac{3}{8} · q^{e} ≤ 𝔼[N] ≤ ℙ[N < \frac{1}{4} · q^{e}] · \frac{1}{4} · q^{e} + ℙ[N ≥ \frac{1}{4} · q^{e}] · 2 · q^{e}

and thus

\frac{3}{8} ≤ (1 − ℙ[N ≥ \frac{1}{4} · q^{e}]) · \frac{1}{4} + ℙ[N ≥ \frac{1}{4} · q^{e}] · 2 = \frac{1}{4} + \frac{7}{4} · ℙ[N ≥ \frac{1}{4} · q^{e}] .

In other words:

ℙ[N ≥ \frac{1}{4} · q^{e}] ≥ \frac{1}{14}

□

After suitable k-vector subspaces U_{i} of K have been computed, the sets F_{i} := {P ∈ E_{a}(𝔽_{q^{n}}) | x(P) ∈ U_{i} − {0}} are enumerated and sorted for the elements in F_{i} (such that given an element of F_{i} one can easily find its number). The factor base is then F := ⋃_{i=1}^{m} F_{i}.

The total expected running time for all these computations is polynomially bounded in n · q^{d}.

3 The new decomposition algorithm

Just as in the predecessor [Die11b] to this work, the relation generation relies on an algorithm to compute “decompositions”, and this algorithm is again based on solving systems of multivariate polynomials over 𝔽_{q}. The definition of a “decomposition” is however different in this work from the previous one. Moreover, we do not use summation polynomials anymore, and more generally, we do not use the projection to a product of projective lines. The reason for this is that by avoiding the projection to projective lines, we can significantly improve the lower bound on the success probability of the relation generation algorithm. This improvement is crucial for the derivation of Theorem 2.

We start with some definitions.

As in the previous section, let q be a prime power, n a natural number at least 2, and let us set k := 𝔽_{q} and K := 𝔽_{q^{n}}. Let E be an elliptic curve in Weierstraß form in x and y over K (with zero point at infinity), and let f(x, y) ∈ K[x, y] be the defining polynomial of the affine part E_{a}. (The notation for the defining polynomial is different from the one in [Die11b].) Let us fix a direct sum decomposition K = ⨁_{i=1}^{m} U_{i} with m ≥ 2 into kvector subspaces. (In this whole section, we do not impose any conditions on x_{|E} or the direct sum decomposition of K, except that the decomposition be non-trivial.) Let F_{i} be defined as above. Finally, let P ∈ E(K).

Definition 3.1 A tuple (P_{1}, …, P_{m}) ∈ F_{1}×⋯×F_{m} with P_{1}+⋯+P_{m} = P is called a decomposition of P with respect to the direct sum decomposition of K.

Let now V_{i} be defined as in the previous section. Then under the isomorphism E(K) ≃ Res_{k}^{K}(E)(k), the set of decompositions of P corresponds to the set of tuples (P_{1}, …, P_{m}) ∈ V_{1}(k) × ⋯ × V_{m}(k) with ∑_{i} P_{i} = P_{⊚} and Res_{k}^{K}(x)(P_{i}) ≠ 0. This is nothing but the set of k-rational points (P_{1}, …, P_{m}) of the fiber at P_{⊚} of the morphism

V_{1} × ⋯ × V_{m} ⟶ Res_{k}^{K}(E)

induced by the addition morphism on Res_{k}^{K}(E) with Res_{k}^{K}(x)(P_{i}) ≠ 0 for all i.

This leads to the next definition.

Definition 3.2 A decomposition (P_{1}, …, P_{m}) of P is called isolated if it corresponds to an isolated (k-rational) point of the fiber (V_{1} × ⋯ × V_{m})_{P_{⊚}} just considered.

The “new decomposition problem” is now the computational problem with the following specification: The input consists of a prime power q, a natural number n, an elliptic curve E ⊆ ℙ_{𝔽_{q^{n}}}^{2} in Weierstraß form with respect to x and y and point at infinity as zero point, a direct sum decomposition 𝔽_{q^{n}} = ⨁_{i=1}^{m} U_{i} of 𝔽_{q^{n}} into 𝔽_{q}-vector subspaces with m ≥ 2 and a point P ∈ E(𝔽_{q^{n}}). The output consists of a list of decompositions of P with respect to the direct sum decomposition of 𝔽_{q^{n}}, containing all isolated decompositions.

For the relation generation, the first crucial result is the following proposition. Furthermore, we need a non-trivial lower bound on the probability that a uniformly randomly distributed point in E(𝔽_{q^{n}}) has an isolated decomposition with respect to the chosen decomposition of K, given that certain conditions are satisfied. Such bounds are established in the next section.

Proposition 3.3

a) There exists an absolute constant C > 0 such that the number of isolated decompositions of some point P ∈ E(𝔽_{q^{n}}) is at most e^{C·mn}.

b) The “new decomposition problem” can be solved in an expected running time which is polynomially bounded in e^{mn} · log(q).

The rest of this section is devoted to the proof of this proposition.

We now give some background information on the idea of the algorithm and address claim a). Computational aspects will be discussed later.

Let us fix an instance as specified in b), and as above, let K|k be the extension of finite fields under consideration.

We first make the following assumption:

x(P) ∉ ⋃_{i=1}^{m} U_{i}

At the end of the section we will discuss an easy modification of the following arguments and the algorithm for the case that x(P) ∈ ⋃_{i=1}^{m} U_{i}.

The main idea is to use the isomorphism E(K) ≃ Cl^{0}(E). Let us use the following notation (cf. [Sil86]): For P ∈ E(K), the prime divisor defined by P is denoted by (P).

For points P_{1}, …, P_{m} ∈ E(K), we have ∑_{i} P_{i} = P if and only if there exists a function g ∈ K(E)^{∗} with (g) = (P_{1})+⋯+(P_{m})+(−P)−(m+1)·(O). Moreover, g is uniquely determined “up to a constant” by the points.

Let us assume that P ≠ O. (For the case P = O, the following considerations can easily be modified.) Let p_{1} := 1, p_{2i} = x^{i}, p_{2i+1} := x^{i−1}y for i ∈ ℕ. Note that for ℓ ∈ ℕ, (p_{1})_{|E}, …, (p_{ℓ})_{|E} is a basis of L(ℓO). Let L_{ℓ} := ⟨p_{1}, …, p_{ℓ}⟩ ∩ {f ∈ k[x, y] | f(−P) = 0}, and let g_{1}, …, g_{m} be a basis of L_{m+1} such that g_{1}, … g_{m−1} is a basis of L_{m}. Then (g_{1})_{|E}, …, (g_{m})_{|E} is a basis of L((m + 1) · (O) − (−P)) and (g_{m})_{|E} ∉ L(m · O − (−P)). Now (P_{1}, …, P_{m}) is a decomposition of P if and only if there exists a tuple (α_{1}, …, α_{m−1}) ∈ K^{m−1} with

(g_{m}+α_{m−1}g_{m−1}+⋯+α_{1}g_{1}) = (P_{1})+⋯+(P_{m})+(−P)−(m+1)·(O) . (14)

Furthermore, there exists at most one such tuple (α_{1}, …, α_{m−1}) in \overline{k}^{m−1}. The set of decompositions of P is thus in canonical bijection to the set of tuples (α_{1}, …, α_{m−1}, P_{1}, …, P_{m}) ∈ K^{m−1} × E_{a}^{m}(K) with x(P_{i}) ∈ U_{i} − {0} such that (14) holds. Note that in any such tuple the points P_{1}, …, P_{m}, P are distinct. (Recall that x(P) ∉ ⋃_{i=1}^{m} U_{i} by assumption).

Let us recall that the defining polynomial of E_{a} is denoted by f. Let now

f_{(i)} := f(x_{i}, y_{i}) ∈ K[x_{1}, y_{1}, …, x_{m}, y_{m}]

for all i = 1, …, m; the scheme V (f_{(1)}, …, f_{(m)}) is therefore equal to E_{a}^{m} in Spec(K[x_{1}, y_{1}, …, x_{m}, y_{m}]).

Let

h := g_{m} + a_{m−1}g_{m−1} + ⋯ a_{1}g_{1} ∈ K[x, y, a_{1}, …, a_{m−1}]

and let

\begin{matrix}h_{(i)} := g_{m}(x_{i}, y_{i}) + a_{m−1}g_{m−1}(x_{i}, y_{i}) + ⋯ + a_{1}g_{1}(x_{i}, y_{i}) \\ ∈ K[a_{1}, …, a_{m−1}, x_{1}, y_{1} …, x_{m}, y_{m}] \end{matrix}

for all i = 1, …, m.

The set of decompositions of P is then in canonical bijection to the set of K-rational points (α_{1}, …, α_{m−1}, P_{1}, …, P_{m}) of the scheme V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}) in Spec(K[a_{1}, …, a_{m−1}, x_{1}, y_{1}, …, x_{m}, y_{m}]) with x(P_{i}) ∈ U_{i} − {0} for all i. Note that we have the canonical projection

V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}) ⟶ V (f_{(1)}, …, f_{(m)}) = E_{a}^{m} ,

given on Z-valued points for any k-scheme Z by

(α_{1}, …, α_{m−1}, P_{1}, …, P_{m}) ↦ (P_{1}, …, P_{m}) .

It is natural to pass to the Weil restriction of V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}) here. Let us first fix some notations: Let W be defined by the diagram

\xymatrix{W \ar@{^{(}->}[r] \ar[d] & Res_{k}^{K}(V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)})) \ar[d] \\ V_{1} × ⋯ × V_{m} \ar[r] \ar@{^{(}->}[r] \ar[d] & (Res_{k}^{K}(E_{a}))^{m} \ar[d] \\ 𝔸_{k}[U_{1}] × ⋯ × 𝔸_{k}[U_{m}] \ar@{^{(}->}[r] & 𝔸_{k}[K]}

being Cartesian. Now the k-rational points of W correspond exactly to the K-rational points (α_{1}, …, α_{m−1}, P_{1}, …, P_{m}) of V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}) with P_{i} ∈ U_{i}.

We now give an explicit description of W via a polynomial system. This description will serve as a basis for the algorithm.

Let b_{1}, …, b_{n} be a k-basis of K. (In the algorithm, such a basis is given with the input.) With this basis, we now identify K with k^{n} and also 𝔸_{k}[K] with 𝔸_{k}^{n}. Moreover, for i = 1, …, m, let b_{i,1}, …, b_{i,dim(U_{i})} be a basis of U_{i}. The scheme W ⊆ Res_{k}^{K}(V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)})) can be described explicitly as follows: Let the polynomials h_{(i),j} and f_{(i),j} for i = 1, …, m, j = 1, …, n in k[(a_{ℓ,j′})_{ℓ=1,...,m−1,j′=1,...,n}, ((x_{i′,j′})_{j′=1,...,dim(U_{i})}, (y_{i′,j′})_{j′=1,...,n})_{i′=1,...,m}] be defined by

h_{(i)}((∑_{j′=1}^{n} a_{ℓ,j′}b_{j′})_{ℓ=1,...,m−1} , ∑_{j′=1}^{dim(U_{i})} x_{i,j′}b_{j′} , ∑_{j′=1}^{n} y_{i,j′}b_{j′}) = ∑_{j=1}^{n} h_{(i),j}b_{j}

and

f_{(i)}( ∑_{j′=1}^{dim(U_{i})} x_{i,j′}b_{i,j′} , ∑_{j′=1}^{n} y_{i,j′}b_{j′}) = ∑_{j′=1}^{n} f_{(i),j}b_{j} .

We have isomorphisms

V_{i} ≃ V ((f_{(i),j})_{j=1,...,n}) ⊆ Spec(k[x_{i,1}, …, x_{i,dim(U_{i})}, y_{i,1}, …, y_{i,n}])

and

W ≃ V ((f_{(i),j})_{i=1,...,m,j=1,...,n}, (h_{(i),j})_{i=1,...,m,j=1,...,n})

(which are canonical for the chosen basis).

The k-rational points of V ((f_{(i),j})_{i=1,...,m,j=1,...,n}, (h_{(i),j})_{i=1,...,m,j=1,...,n}) correspond in an obvious way to the K-rational points (a_{1}, …, a_{m−1}, P_{1}, …, P_{m}) of V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}) with x(P_{i}) ∈ U_{i}. Such points with x(P_{i}) ∈ U_{i} − {0} then correspond to the decompositions of P.

We have a polynomial system in 2mn variables and 2mn equations.

We want to obtain a suitable polytope which contains the exponents in the support of the system.

Let us first consider the total degrees of h_{(i),j} and f_{(i),j} with respect to the three systems of variables (a_{ℓ,j′})_{ℓ,j′}, (x_{i′,j′})_{i′,j′} and (y_{i,j′})_{i,j′}. Concerning the h_{(i),j} we have: the total degree with respect to the a_{ℓ,j′} is at most 1, the total degree with respect to the x_{i′,j′} is at most ⌊\frac{m}{2}⌋, the total degree with respect to the y_{i′,j′} is at most 1. Concerning the f_{(i),j} we have: The total degree with respect to the x_{i′,j′} is at most 3, the total degree with respect to the y_{i′,j′} is at most 2.

We now consider the a_{ℓ,j′} and the y_{i′,j′} as one system of variables and the x_{i′,j′} as another system of variables. So we have 2·(m−1)·n variables in the first system and the total degrees of all polynomials under consideration with respect to this system are at most 2. Furthermore, we have n variables in the second system and the total degrees with respect to this system are at most max(3, ⌊\frac{m}{2}⌋).

Let Δ_{ℓ} := \{\underline{x} ∈ ℝ_{≥0}^{ℓ} | ∑_{i} x_{i} ≤ 1\}. With a suitable numeration, the exponents are contained in the polytope

P := 2 · Δ_{(2m−1)·n} × max(3, ⌊\frac{m}{2}⌋) · Δ_{n} .

The toric variety T (P) defined by this polytope is ℙ_{k}^{(2m−1)·n} × ℙ_{k}^{n}. The volume of the polytope is 2^{(2m−1)·n} · \frac{1}{((2m−1)·n)!} · max(3, ⌊\frac{m}{2}⌋)^{n} · \frac{1}{n!}. The system of equations defines a system of sections of a line bundle on T (P), and the degree of the 0-cycle in the Chow ring of T (P) defined by this system is (2mn)! times the volume of the polytope, that is,

2^{(2m−1)·n} · max(3, ⌊\frac{m}{2}⌋)^{n} · \binom{2mn}{n}

< 2^{(2m−1)·n} · max(3, ⌊\frac{m}{2}⌋)^{n} · 2^{2mn} < 2^{4mn} · max(3, \frac{m}{2})^{n} .

Therefore the scheme defined by the sections on T (P) associated to the equations has at most 2^{4mn}·max(3, \frac{m}{2})^{n} isolated \overline{k}-rational points. We have a natural embedding of 𝔸_{k}^{2mn} into T (P), and the sections restrict to the equations under this embedding. Thus the scheme V ((f_{(i),j})_{i=1,...,m,j=1,...,n}, (h_{(i),j})_{i=1,...,m,j=1,...,n}) has at most 2^{4mn} · max(3, \frac{m}{2})^{n} ∈ e^{O(mn)} isolated \overline{k}-rational points.

Let us now turn to algorithmic aspects: It is straightforward to compute a system (f_{(i),j})_{i=1,...,m,j=1,...,n}, (h_{(i),j})_{i=1,...,m,j=1,...,n} as above. We then use Rojas’ algorithm ([Roj99]) for sparse polynomial systems to determine all isolated k-rational solutions. The input and output structure as well as the running time of the algorithm are given in [Roj99, Main Theorem 2.1]; all the following statements on the algorithm refer to this theorem.

We apply the algorithm with the system of equations and the polytope P defined above. The output of the algorithm is a system of univariate polynomials h, h_{1}, …, h_{2mn} the degrees of which are all bounded by the degree of the 0-cycle defined by the given system of sections in the Chow ring of T (P) and thus by 2^{4mn} · max(3, \frac{m}{2})^{n}. By factoring h and applying the system h_{1}, …, h_{2mn} to the rational roots, we obtain a list of points in k^{2mn}. This list consists of solutions to the system and contains all isolated k-rational solutions of the system on 𝔸_{k}^{2mn}.

The running time of Rojas’ algorithm is polynomially bounded in e^{m·n} · log(q), and in an expected time which is also polynomially bounded in e^{m·n} · log(q) we can factor the univariate polynomial h. Explicitly, the running time of Rojas’ algorithm depends on mixed volumes of various systems of polytopes all of which are contained in the polytope P. Therefore these mixed volumes are also bounded by 2^{4mn} · max(3, \frac{m}{2})^{n}.

We obtain the following intermediate result:

Lemma 3.4

a) A system (f_{(i),j})_{i=1,...,m,j=1,...,n}, (h_{(i),j})_{i=1,...,m,j=1,...,n} as above has e^{O(mn)} isolated k-rational solutions.

b) Given an instance of the “new decomposition problem”, one can compute a system (f_{(i),j})_{i=1,...,m,j=1,...,n}, (h_{(i),j})_{i=1,...,m,j=1,...,n} as above and a list of k-rational solutions, containing all isolated k-rational solutions, in an expected time which is polynomially bounded in e^{mn} · log(q).

This is however not yet the statement we want to prove. Indeed, we still have to show that in this way we can obtain a list of decompositions of P which contains all isolated decompositions.

Let P ∈ E_{a}(K).

We first study the geometric fibers of the morphism

V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}) ⟶ V (f_{(1)}, …, f_{(m)}) = E_{a}^{m} .

Let (P_{1}, …, P_{m}) ∈ E_{a}^{m}(\overline{k}) such that the points P_{1}, …, P_{m}, P_{⊚} are distinct. Then there is at most one tuple (α_{1}, …, α_{m−1}) ∈ \overline{k}^{m} such that (14) holds, depending on whether ∑_{i} P_{i} = P_{⊚} or not.

Let now D be the closed subscheme of E_{a}^{m} given on Z-valued points for any k-scheme Z by

D(Z) = {(P_{1}, …, P_{m}) ∈ E_{a}^{m}(Z) | ∃i ≠ i′ : P_{i} = P_{i′} or ∃i : P_{i} = P } .

Let T := E_{a}^{m}−D and let S be the preimage of T in V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)}). Now the morphism S ⟶ T induces an injection on the sets of geometric points and its image consists of those points (P_{1}, …, P_{m}) ∈ E_{a}^{m}(\overline{k}) with ∑_{i} P_{i} = P_{⊚}.

We consider the restriction of the m-fold addition morphism E^{m} ⟶ E to T. Following the usual notation, let T_{P} be the fiber of this morphism at P. This is an open subscheme of a scheme isomorphic to E^{m−1}.

The morphism S ⟶ T induces a bijection S(\overline{k}) ⟶ T_{P} (\overline{k}). As T_{P} is reduced, we have an induced morphism S ⟶ T_{P}.

We now pass to Weil restrictions. Note first that we again have the addition Res_{k}^{K}(E)^{m} ⟶ Res_{k}^{K}(E) and the fiber (Res_{k}^{K}(E)^{m})_{P_{⊚}}.

We have a canonical open embedding

Res_{k}^{K}(T) ⊆ Res_{k}^{K}(E_{a}^{m}) ≃ (Res_{k}^{K}(E_{a}))^{m} .

Note that under the canonical isomorphism Res_{k}^{K}(E_{a})^{m}(k) ≃ E_{a}^{m}(K), the points of Res_{k}^{K}(T)(k) correspond to the points (P_{1}, …, P_{m}) ∈ E^{m}(K) which are contained in T (K), that is, to points (P_{1}, …, P_{m}) ∈ E^{m}(K) such that the points P_{1}, …, P_{m}, P are distinct.

Let

V^{∗} := (V_{1} × ⋯ × V_{m}) ∩ Res_{k}^{K}(T) ⊆ (Res_{k}^{K}(E_{a}))^{m}

and let V_{P_{⊚}}^{∗} be the fiber of P_{⊚} under the restriction of the addition morphism Res_{k}^{K}(E)^{m} ⟶ Res_{k}^{K}(E) to V^{∗}. We have

V_{P_{⊚}}^{∗} = V^{∗} ∩ (Res_{k}^{K}(E_{a})^{m})_{P_{⊚}} = V^{∗} ∩ Res(T)_{P_{⊚}} .  (15)

Let now P ∉ ⋃_{i=1}^{m} U_{i}. The set of k-rational points of V^{∗} contains all k-rational points of Res_{k}^{K}(E_{a})^{m} corresponding to decompositions of P. (There might be more points in V^{∗}(k) because there might be k-rational points (P_{1}, …, P_{m}) of V^{∗} with x_{i}(P) = 0 for some i ∈ {1, …, m}.) As Res_{k}^{K}(T) is open in Res_{k}^{K}(E_{a})^{m}, a k-rational point of V_{1}^{∗}×⋯×V_{m}^{∗} is open in V_{1}^{∗} × ⋯ × V_{m}^{∗} if and only if it is open in V_{1} × ⋯ × V_{m}. Therefore, the set of isolated k-rational points of V^{∗} contains all k-rational points of Res_{k}^{K}(E_{a})^{m} corresponding to isolated decompositions of P.

Let W^{∗} be the preimage of V^{∗} in Res_{k}^{K}(V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)})). Our goal is to show that the preimages of the isolated k-rational points of V^{∗} are isolated k-rational points of W^{∗}.

We have the Cartesian diagram

\xymatrix{Res_{k}^{K}(S) \ar[d] \ar@{^{(}->}[r] & Res_{k}^{K}(V (f_{(1)}, …, f_{(m)}, h_{(1)}, …, h_{(m)})) \ar[d] \\ Res_{k}^{K}(T) \ar@{^{(}->}[r] & Res_{k}^{K}(E_{a}^{m}) ≃ Res_{k}^{K}(E_{a})^{m} .}

Moreover, as the morphism S ⟶ T factors through the fiber T_{P}, by functoriality, the morphism Res_{k}^{K}(S) ⟶ Res_{k}^{k}(T) factors through the fiber Res_{k}^{K}(T)_{P_{⊚}}. We claim that we have an induced bijection between Res_{k}^{K}(S)(\overline{k}) and Res_{k}^{K}(T)_{P_{⊚}}(\overline{k}). For this, we can (obviously) apply the base change to \overline{k}|k. But over \overline{k}, the two Weil restrictions become products of Galois twists of S and T, and we have already shown the claim for the factors of the product. The claim thus follows. By considering the Galois operation, we obtain that for every algebraic field extension λ|k we have a bijection between Res_{k}^{K}(S)(λ) and (Res_{k}^{k}(T))_{P_{⊚}}(λ). We are going to use this for λ = k.

As V^{∗} is contained in Res_{k}^{K}(T), W^{∗} is contained in Res_{k}^{K}(S), and we have a Cartesian diagram

\xymatrix{W^{∗} \ar[d] \ar@{^{(}->}[r] & Res_{k}^{K}(S) \ar[d] \\ V^{∗} \ar@{^{(}->}[r] & Res_{k}^{K}(T) .}

The composition W^{∗} ⟶ Res_{k}^{K}(T) (obviously) factors through V^{∗} and – as we have just seen – it factors through (Res_{k}^{K}(T))_{P_{⊚}}. By (15) it factors through V_{P_{⊚}}^{∗}. The morphism

W^{∗} ⟶ V_{P_{⊚}}^{∗}

again induces a bijection

W^{∗}(k) ⟶ V_{P_{⊚}}^{∗}(k) .

Let now (P_{1}, …, P_{m}) be an isolated k-rational point of V^{∗}. This is a k-rational point of V^{∗} which is open in V^{∗}. Then the fiber over (P_{1}, …, P_{m}) in W^{∗} is open in W^{∗}, and it is a k-rational point. Therefore it is an isolated k-rational point of W^{∗} and also of W.

We note again that for any isolated decomposition of P the corresponding point in (V_{1} × ⋯ × V_{m})(k) lies in V^{∗}(k) and is isolated. Therefore every isolated decomposition of P defines an isolated k-rational point of W.

This finishes the proof of Proposition 3.3 under the assumption that x(P) ∉ ⋃_{i=1}^{m} U_{i}.

Modification for x(P) ∈ ⋃_{i=1}^{m} U_{i}

We now discuss the modification for the case that x(P) ∈ ⋃_{i=1}^{m} U_{i}. Except for finitely many instances, there exists a point R ∈ E_{a}(K) with x(R) ∉ ⋃_{i=1}^{m} U_{i} and x(P − R) ∉ ⋃_{i=1}^{m} U_{i}.

Let us fix such a point R and let S := P − R. Let L̃_{ℓ} := ⟨p_{1}, …, p_{ℓ}⟩ ∩ {f ∈ k[x, y] | f(−R) = 0 , f(−S) = 0}. Let g̃_{1}, …, g̃_{m} be a basis of L̃_{m+2} such that g̃_{1}, …, g̃_{m−1} is a basis of L_{m+1}. Now a tuple (P_{1}, …, P_{m}) ∈ F_{1} × ⋯ × F_{m} is a decomposition of P if and only if there exists a tuple (α_{1}, …, α_{m−1}) ∈ K^{m−1} with

(g̃_{m}+α_{m−1}g̃_{m−1}+⋯+α_{1}g̃_{1}) = (P_{1})+⋯+(P_{m})+(−R)+(−S)−(m+1)·(O) .

Moreover, if such a tuple exists, it is unique. With this modifications, we obtain again the desired bound on the number of isolated decompositions. Moreover, by choosing a point R ∈ E_{a}(K) uniformly randomly, we also obtain the algorithmic result. Note here that if P is in the factor base, we immediately have a relation, so we do not need to apply the decomposition algorithm. The bound on the number of isolated decompositions will however be used later.

4 Analysis and the final result

Let K|k and E/K be as above and m ∈ ℕ with 2 ≤ m ≤ \frac{n}{2}. We assume that Condition 2.1 is satisfied. Furthermore, let a decomposition K = ⨁_{i=1}^{m} U_{i} be given which satisfies the conditions in subsection 2.5. Moreover, let F_{i} and V_{i} be as above.

As in subsection 2.3, let P_{0} ∈ E(K) be one of the two points in E(K) lying over 0.

We want to obtain a lower bound on the number of points P ∈ E(K) which have isolated decompositions. For this goal, we first want to derive an upper bound on the number of tuples (P_{1}, …, P_{m}) ∈ F_{1} × ⋯ × F_{m} which define non-isolated decompositions.

Let a_{m} : Res_{k}^{K}(A) ⟶ Res_{k}^{K}(E) be the m-fold addition morphism and a′_{m} : V_{1} × ⋯ × V_{m} ⟶ Res_{k}^{K}(E) the restriction of a_{m} to V_{1} × ⋯ × V_{m}.

We now consider a point (P_{1}, …, P_{m}) ∈ E^{m}(K) with x(P_{i}) ∈ U_{i} and let P := ∑_{i=1}^{m} P_{i}.

The morphism a′_{m} : V_{1} × ⋯ × V_{m} ⟶ Res_{k}^{K}(E) is unramified at ((P_{1})_{⊚}, …, (P_{m})_{⊚}) if and only if ((P_{1})_{⊚}, …, (P_{m})_{⊚}) is an isolated reduced point of the fiber at P_{⊚}. We ask ourselves for which tuples (P_{1}, …, P_{m}) as above the morphism is ramified at ((P_{1})_{⊚}, …, (P_{m})_{⊚}). As already pointed out in the proof of Proposition 2.2 the morphism a′_{m} : V_{1} × ⋯ × V_{m} ⟶ Res_{k}^{K}(E) is unramified at ((P_{1})_{⊚}, …, (P_{m})_{⊚}) if and only if the induced map on tangent spaces

(a′_{m})_{∗} : T_{((P_{1})_{⊚},...,(P_{m})_{⊚})}(V_{1} × ⋯ × V_{m}) ⟶ T_{P_{⊚}}(V_{1} × ⋯ × V_{m})

is injective.

We now consider points (P_{1}, …, P_{m}) ∈ E(K)^{m} with x(P_{i}) ∈ U_{i} for all i which satisfy the following condition.

Condition 4.1 The flat covering x_{|E} is unramified at P_{1}, …, P_{m}.

This condition is equivalent to the condition that for every i, the flat covering Res_{k}^{K}(E_{a}) ⟶ Res_{k}^{K}(𝔸_{k}^{1}) is unramified at (P_{i})_{⊚}. By base change, this implies that for every i, V_{i} ⟶ 𝔸_{k}[U_{i}] is unramified (and thus étale) at (P_{i})_{⊚}. Therefore, V_{i} is smooth at (P_{i})_{⊚} and we have an isomorphism of tangent spaces T_{(P_{i})_{⊚}}(V_{i}) ⟶ T_{(x(P_{i}))_{⊚}}(𝔸_{k}[U_{i}]).

Let such a point (P_{1}, …, P_{m}) be given and let again P := ∑_{i=1}^{m} P_{i}. By Lemma 2.4 we have a commutative diagram

\xymatrix{T_{((P_{1})_{⊚},...,(P_{m})_{⊚})}(V_{1} × ⋯ × V_{m}) \ar[r]^{(a′_{m})_{∗}} \ar[d]_{(τ_{(P_{0}−P_{1})_{⊚},...,(P_{0}−Pm)_{⊚}})_{∗}} & T_{P_{⊚}}(Res_{k}^{K}(E)) \ar[d]^{(τ_{m·(P_{0}−P)_{⊚}})_{∗}} \\ T_{((P_{0})_{⊚},...,(P_{0})_{⊚})}(V_{1} × ⋯ × V_{m}) \ar[r]^{(a′_{m})_{∗}} \ar[d] & T_{m(P_{0})_{⊚}}(Res_{k}^{k}(E)) \\ T_{(P_{0})_{⊚}}(V_{1}) × ⋯ × T_{(P_{0})_{⊚}}(V_{m}) \ar[r] & T_{(P_{0})_{⊚}}(Res_{k}^{k}(E)) \ar[u]_{(τ_{(m−1)·(P_{0})_{⊚}})_{∗}}}

where the lower map is the addition on tangent spaces. Moreover, by the proof of Proposition 2.2, the two lower vertical homomorphisms are isomorphisms. Under the isomorphism T_{(P_{1})_{⊚}}(V_{1}) × ⋯ × T_{(P_{m})_{⊚}}(V_{m}) ≃ T_{((P_{1})_{⊚},...,(P_{m})_{⊚})}(V_{1} × ⋯ × V_{m}), the horizontal map on the left hand side is

\begin{matrix}(τ_{(P_{0}−P_{1})_{⊚}})_{∗} × ⋯ × (τ_{(P_{0}−P_{m})_{⊚}})_{∗} : T_{(P_{1})_{⊚}}(V_{1}) × ⋯ × T_{(P_{m})_{⊚}}(V_{m}) ⟶ \\ T_{(P_{0})_{⊚}}(V_{1}) × ⋯ × T_{(P_{0})_{⊚}}(V_{m}) . \end{matrix}

So the morphism (a′_{m})_{∗} is unramified at ((P_{1})_{⊚}, …, (P_{m})_{⊚}) if and only if we have a direct sum decomposition

T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)) = ⨁_{i=1}^{m} (τ_{(P_{0}−P_{i})_{⊚}})_{∗}(T_{(P_{i})_{⊚}}(V_{i})) .  (16)

We want to derive a condition under which we do have such a decomposition. For this, we distinguish between three cases: q odd; q even and j ≠ 0; and q even and j = 0.

The case that q is odd

We need some facts on tangent vectors of the projective line and the elliptic curve E. Here and in the following we assume that the defining polynomial f of E_{a} is of the form y^{2} − v(x) (with v monic of degree 3).

Following our usual notation, let ℙ_{K}^{1} := Proj(K[X, Y]). We set x_{ℙ^{1}} := \frac{X}{Y} ∈ K(ℙ^{1}) (such that K(ℙ^{1}) = K(x_{ℙ^{1}})).

On ℙ_{K}^{1}, we have the meromorphic cotangent vector field dx_{ℙ^{1}} with divisor −2∞. Under duality, this corresponds to a tangent vector field which we denote by t_{ℙ^{1}} ∈ Γ(ℙ_{k}^{1}, T_{ℙ_{k}^{1}}) and which has divisor 2∞.

Let R be the ramification divisor of the covering x_{|E}. Then the meromorphic cotangent vector field dx_{|E} has divisor −4(O) + R, and we have the holomorphic cotangent vector field \frac{dx_{|E}}{y_{|E}}. This field is invariant under

translation, that is, for every translation τ of E we have τ^{∗}(\frac{dx_{|E}}{y_{|E}}) = \frac{dx_{|E}}{y_{|E}}.

Again under duality, dx_{|E} corresponds to a meromorphic tangent vector field; we denote this by t_{E}. It has divisor 4(O) − R. So we have the holomorphic tangent vector field y_{E} t_{E}, which corresponds to \frac{dx_{|E}}{y_{|E}} under duality. Moreover, the field y_{E} t_{E} is also invariant under translation, that is, for every translation τ of E, τ_{∗}(y_{|E} t_{E}) = y_{|E} t_{E}.

Following the notation fixed in the introduction, for some point P ∈ E(K), we denote the tangent vector in T_{P} (E) induced by t_{E} by t_{E}(P).

Let two K-rational points P_{0} and P_{1} of E which are not ramification points under x_{|E} be given and let us consider the homomorphism (τ_{P_{0}−P_{1}})_{∗} : T_{P_{1}}(E) ⟶ T_{P_{0}}(E). This homomorphism is given by y(P_{1}) t_{E}(P_{1}) ↦ y(P_{0}) t_{E}(P_{0}), that is,

t_{E}(P_{1}) ↦ \frac{y(P_{0})}{y(P_{1})} t_{E}(P_{0}) .  (17)

As in the previous section, Let us fix a basis (b_{j})_{j} of K over k and bases (b_{i,j})_{j} of the U_{i}. Let us denote the corresponding dual bases by (x_{j})_{j} and (x_{i,j})_{j}. The bases (b_{j})_{j} and (b_{i,j})_{j} define bases of the spaces Γ(𝔸_{k}[K], T ) and Γ(𝔸_{k}[U_{i}], T ). We denote these bases by (t_{j})_{j=1,...,n} for 𝔸_{k}[K] and (t_{i,j})_{j=1,...,dim(U_{i})} for 𝔸_{k}[U_{i}].

Let P ∈ E(K) such that x_{|E} is unramified at P. Then Res_{k}^{K}(x_{|E_{a}}) defines an isomorphism of tangent spaces (Res_{k}^{K}(x_{|E_{a}}))_{∗} : T_{P_{⊚}}(Res_{k}^{K}(x_{|E_{a}})) ⟶ T_{x(P)_{⊚}}(𝔸[K]). Now for t ∈ Γ(𝔸[K], T ), we define t(P_{⊚}) := ((Res_{k}^{K}(x_{|E_{a}}))_{∗})^{−1}(t(x(P)_{⊚})). The isomorphism of tangent vector spaces restricts to an isomorphism of tangent vector spaces T_{P_{⊚}}(V_{i}) ⟶ T_{x(P)_{⊚}}(𝔸[U_{i}]). Thus t(P_{⊚}) is in T_{P_{⊚}}(V_{i}) if and only if t(x(P)_{⊚}) is in T_{x(P)_{⊚}}(𝔸[U_{i}]).

Just as the bases (t_{j}(x(P)_{⊚}))_{j} and (d(x_{j})(x(P)_{⊚}))_{j} are dual to each other, so are the bases (t_{j}(P_{⊚}))_{j} and (d(x_{j})_{| Res_{k}^{K}(E_{a})}(P_{⊚}))_{j}.

Let A_{i} be the coordinate matrix of (b_{i,j})_{j} with respect to (b_{j})_{j}. Then this is also the coordinate matrix of (t_{i,j})_{j} with respect to (t_{j})_{j}, and for any P ∈ E(K) as above, it is also the coordinate matrix of (t_{i,j}(P_{⊚}))_{j} with respect to (t_{j}(P_{⊚}))_{j}. For the following, it is important that the matrix does not depend on P.

Let now (P_{1}, …, P_{m}) ∈ E^{m}(K) with x(P_{i}) ∈ U_{i} for all i satisfy Condition 4.1. Then for each i = 1, …, m, the system (t_{i,j}((P_{i})_{⊚}))_{j} is a basis of the k-vector space T_{(P_{i})_{⊚}}(V_{i}). We have a direct sum decomposition of T_{(P_{0})_{⊚}}(Res_{k}^{K}(E)) as in (16) if and only if the elements (t_{(P_{0}−P_{i})_{⊚}})_{∗}(t_{i,j}((P_{i})_{⊚})) for i = 1, …, m, j = 1, …, dim(U_{i}) form a k-basis of T_{P_{⊚}}(Res_{k}^{K}(E)).

Let for j = 0, …, n − 1 f_{j} ∈ k[x_{1}, …, x_{n}, y_{1}, …, y_{n}] be defined by f = ∑_{j=1}^{n} b_{j} · f_{j}. Let u : (Res_{k}^{K}(E_{a}))_{K} ⟶ E_{a} be the universal morphism. We have the isomorphism

(u, σ(u), …, σ^{n−1}(u)) : (Res_{k}^{K}(E_{a}))_{K} ˜ ⟶ ∏_{s=0}^{n−1} σ_{K|k}^{s}(E_{a})  (18)

corresponding to the isomorphism of K-algebras

⨂_{s=0}^{n−1} K[x^{(s)}, y^{(s)}]/(σ_{K|k}^{s}(f)(x^{(s)}, y^{(s)})) ˜ ⟶K[x_{1}, …, x_{n}, y_{1}, …, y_{n}]/(f_{1}, …, f_{n}) ,

x^{(s)} ↦ ∑_{j=1}^{n} σ_{K|k}^{s}(b_{j}) · x_{j} , y^{(s)} ↦ ∑_{j=1}^{n} σ_{K|k}^{s}(b_{j}) · y_{j} .

Note that for P ∈ E(K), under isomorphism (18) the point P_{⊚} ∈ Res_{k}^{k}(E)(k) ⊆ Res_{k}^{K}(E)(K) corresponds to the point (σ^{s}(P))_{s=0,...,n−1} ∈ ∏_{s=0}^{n−1} σ_{K|k}^{s}(E_{a})(K).

We have an induced isomorphism Γ(Res_{k}^{K}(E_{a})_{K}, Ω) ≃ ⨁_{s=0}^{n−1} Γ(σ^{s}(E_{a}), Ω) under which d(x^{(s)})_{|σ^{s}(E_{a})} corresponds to ∑_{j=1}^{n} σ_{K|k}^{s}(b_{j}) · d(x_{j})_{| Res_{k}^{K}(E_{a})}. This isomorphism induces an isomorphism between the cotangent spaces at P_{⊚} and (σ^{s}(P))_{s=0,...,n−1}. Let again x_{|E} be unramified at P. If we then apply the duality between cotangent and tangent spaces, we obtain that t_{j}(P_{⊚}) corresponds to (σ_{K|k}^{s}(b_{j})·t_{σ^{s}(E_{a})}(σ^{s}(P)))_{s=0,...,n−1} under the induced isomorphism of tangent spaces at P_{⊚} and (σ^{s}(P))_{s=0,...,n−1}.

On each of the factors of the product ∏_{s=0}^{n−1} σ_{K|k}^{s}(E_{a}), we can apply the considerations above. We obtain that (τ_{(P_{0}−P_{i})_{⊚}})_{∗}(t_{j}((P_{i})_{⊚})) corresponds to

((τ_{(σ(P_{0})−σ(P_{i}))})_{∗}(σ_{K|k}^{s}(b_{j}) · t_{σ^{s}(E_{a})}(σ^{s}(P_{0}))))_{s=0,...,n−1}

= (σ_{K|k}^{s}(b_{j}) · \frac{y^{(s)}(σ(P_{0}))}{y^{(s)}(σ(P_{i}))} · t_{σ^{s}(E_{a})}(σ^{s}(P_{0})))_{s=0,...,n−1}

= (σ_{K|k}^{s}(b_{j}) · \frac{∑_{ℓ=1}^{n} σ_{K|k}^{s}(b_{ℓ}) · y_{ℓ}((P_{0})_{⊚})}{∑_{ℓ=1}^{n} σ_{K|k}^{s}(b_{ℓ}) · y_{ℓ}((P_{i})_{⊚})} · t_{σ^{s}(E_{a})}(σ^{s}(P_{0})))_{s=0,...,n−1} .

This vector is of course invariant under the Galois operation of K|k. Let C be the inverse of the matrix ((σ^{s}(b_{j})))_{s=0,...,n−1,j=1,...,n}; this is a matrix of the form ((σ^{s}(c_{u})))_{u=1,...,n,s=0,...,n−1}. Going back, we have

(τ_{(P_{0}−P_{i})_{⊚}})_{∗}(t_{j}((P_{i})_{⊚}))

= ∑_{s=0}^{n−1} σ_{K|k}^{s}(b_{j}) · \frac{∑_{ℓ=1}^{n} σ_{K|k}^{s}(b_{ℓ}) · y_{ℓ}((P_{0})_{⊚})}{∑_{ℓ=1}^{s} σ_{K|k}^{s}(b_{ℓ}) · y_{ℓ}((P_{i})_{⊚})} · (∑_{u=1}^{n} σ^{s}(c_{u})(t_{u}((P_{0})_{⊚})))

= ∑_{u=1}^{n} ∑_{s=0}^{n−1} σ_{K|k}^{s}(b_{j} · \frac{∑_{ℓ=1}^{n} b_{ℓ} · y_{ℓ}((P_{0})_{⊚})}{∑_{ℓ=1}^{s} b_{ℓ} · y_{ℓ}((P_{i})_{⊚})} · c_{u}) · (t_{u}(P_{0})_{⊚}) .

Let c_{j,u} := b_{j}c_{u} ·(∑_{ℓ=1}^{n} b_{ℓ} ·y_{ℓ}(P_{0})_{⊚}) ∈ K. (Note here that these constants are independent of P_{1}, …, P_{m}.) Then

\begin{matrix}(τ_{(P_{0}−P_{i})_{⊚}})_{∗}(t_{j}((P_{i})_{⊚})) \\ = ∑_{u=1}^{n} ∑_{s=0}^{n−1} σ_{K|k}^{s}(\frac{c_{j,u}}{∑_{ℓ=1}^{n} b_{ℓ} · y_{ℓ}((P_{i})_{⊚})}) · t_{u}((P_{0})_{⊚}) . \end{matrix}

Let ι_{i} : V_{i} ↪ Res_{k}^{K}(E) be the immersions. It follows that there are constants c_{i,j,u} ∈ K (again independent of P_{1}, …, P_{m}) with

((τ_{(P_{0}−P_{i})_{⊚}})_{∗} ∘ (ι_{i})_{∗})t_{i,j}((P_{i})_{⊚})

= ∑_{u=1}^{n} ∑_{s=0}^{n−1} σ_{K|k}^{s}(\frac{c_{i,j,u}}{∑_{ℓ=1}^{n} b_{ℓ} · y_{i,ℓ}((P_{i})_{⊚})}) · t_{u}((P_{0})_{⊚})

= ∑_{u=1}^{n} ∑_{s=0}^{n−1} (\frac{σ_{K|k}^{s}(c_{i,j,u})}{∑_{ℓ=1}^{n} σ_{K|k}^{s}(b_{ℓ}) · y_{i,ℓ}((P_{i})_{⊚})}) · t_{u}((P_{0})_{⊚}) .

Let

M_{0} := (( ∑_{s=0}^{n−1} \frac{σ_{K|k}^{s}(c_{i,j,u})}{∑_{ℓ=1}^{n} σ_{K|k}^{s}(b_{ℓ}) · y_{i,ℓ}} ))_{u=1,...,n , (i=1,...,m,j=1,...,dim(U_{i}))}

∈ k((y_{i′,j′})_{i′=1,...,m,j′=1,...,n})^{{1,...,n}×(⋃_{i=1}^{m} ⋃_{j=1}^{dim(U_{i})}{(i,j)})} .

Note here that as indicated M_{0} is a matrix over k((y_{i′,j′})_{i′=1,...,m,j′=1,...,n} because the entries are invariant under the Galois operation. The matrix has the size n×n. It is however more convenient to use the indicated indices for the columns. Note further that for no (P_{1}, …, P_{m}) ∈ E^{m}(K) with x(P_{i}) ∈ U_{i} for all i satisfying Condition 4.1 and for no i, s, ∑_{ℓ=1}^{n} σ^{s}(b_{ℓ}) · y_{i,ℓ} vanishes at ((P_{1})_{⊚}, …, (P_{n})_{⊚}).

We have a direct sum decomposition of T_{0}(Res_{k}^{K}(E)) as in (16) if and only if the matrix M_{0}((P_{1})_{⊚}, …, (P_{n})_{⊚}) is non-singular.

By Proposition 2.2 we know that this matrix is non-singular for (P_{1}, …, P_{n}) = (P_{0}, …, P_{0}). In particular, the matrix M_{0} itself is nonsingular.

We now multiply the columns of M by polynomials such that the entries of the resulting matrix are polynomials. Concretely, we multiply all columns with column index (i, j) with the polynomial ∏_{t=0}^{n−1}(∑_{ℓ=1}^{n} σ_{K|k}^{t}(b_{ℓ})·y_{i,ℓ}). The resulting matrix is

M =

(( ∑_{s=0}^{n−1} σ_{K|k}^{s}(c_{i,j,u}) · ∏_{\begin{matrix}t = 0 \\ t ≠ s \end{matrix}}^{n−1} ( ∑_{ℓ=1}^{n} σ_{K|k}^{t}(b_{ℓ}) · y_{i,ℓ})))_{u=1,...,n , (i=1,...,m,j=1,...,dim(U_{i}))}

∈ k[(y_{i′,j′})_{i′=1,...,m,j′=1,...,n}] .

Let d := det(M) ∈ k[(y_{i′,j′})_{i′,j′}]. Again for (P_{1}, …, P_{m}) as above, d vanishes at ((P_{1})_{⊚}, …, (P_{m})_{⊚}) if and only if the homomorphism a′_{m} is unramified at ((P_{1})_{⊚}, …, (P_{m})_{⊚}). Furthermore d does not vanish identically on V_{1}, × ⋯ × V_{m} because it does not vanish at ((P_{0})_{⊚}, …, (P_{0})_{⊚}).

We want to study the vanishing locus of d on V_{1} × ⋯ × V_{m} and derive an upper bound on the number of k-rational points in the locus.

An entry of M with column index (i, j) is a homogeneous polynomial in the variables y_{i,1}, …, y_{i,n} of degree n − 1. Therefore d is multihomogeneous with respect to the sets of variables (y_{i,1}, …, y_{i,n})_{i=1,...,m} of multidegree (dim(U_{1}) · (n − 1), …, dim(U_{m}) · (n − 1)). The total degree is therefore n^{2} − n. We want to prove:

Proposition 4.2 The number of k-rational points in the locus of d on V_{1} × ⋯ × V_{m} is at most n^{5} · 4^{n} · q^{n−1}.

Proof. Let us first mention the following general fact.

Lemma 4.3 Let f be a non-trivial polynomial in 𝔽_{q}[x_{1}, …, x_{n}] of total degree d. Then V (f) contains at most d · q^{n−1} 𝔽_{q}-rational points.

Proof. As 𝔽_{q}[x_{1}, …, x_{n}] is factorial, we are immediately reduced to the case that f is irreducible. If now f = x_{n} − a for some a ∈ 𝔽_{q}, we are done. Let us assume that this is not the case and let a ∈ 𝔽_{q}. Now f is not divisible by x_{n} − a. This means that not every coefficient of f as a polynomial in 𝔽_{q}[x_{n}][x_{1}, …, x_{n−1}] is divisible by x_{n} − a, in other words, the polynomial f(x_{1}, …, x_{n−1}, a) is non-trivial. The result now follows by induction on n. □

We will use resultants to eliminate the “y-variables”. Let us consider the polynomials f, f_{j} and f_{(i),j} as polynomials in the “y-variables”. Now let

F := Z^{2} · f(x, \frac{Y}{Z}) ∈ K[x][Y, Z] ,

F_{j} := Z^{2} · f_{j}(x_{1}, …, x_{n}, \frac{Y_{1}}{Z} , …, \frac{Y_{n}}{Z}) ∈ k[x_{1}, …, x_{n}][Y_{1}, …, Y_{n}, Z] ,

F_{(i),j} := Z^{2} · f_{(i),j}(x_{i,1}, …, x_{i,dim(U_{i})}, \frac{Y_{i,1}}{Z} , …, \frac{Y_{i,n}}{Z})

∈ k[x_{i,1}, …, x_{i,dim(U_{i})}][Y_{i,1}, …, Y_{i,n}, Z]

be the homogeneous polynomials of degree 2 obtained by “homogenizing with respect to the y-variables to a homogeneous degree 2 polynomial”.

Let us consider k[x][Y, Z], k[x_{1}, … x_{n}][Y_{1}, …, Y_{n}, Z] and k[x_{i,1}, …, x_{i,dim(U_{i})}][Y_{i,1}, …, Y_{i,n}, Z] as graded rings in the second set of variables. Let \overline{V}_{i} be the scheme defined by (F_{(i),j})_{j=1,...,n} in Proj(k[x_{i,1}, …, x_{i,dim(U_{i})}][Y_{i,1}, …, Y_{i,n}, Z]) ≃ 𝔸_{k}^{dim(U_{i})} ×ℙ_{k}^{n}. We have a commutative diagram of canonical embeddings

\xymatrix{V_{i} \ar@{^{(}->}[r] \ar@{^{(}->}[d] & \overline{V}_{i} \ar@{^{(}->}[d] \\ Res_{k}^{K}(E) = V (f_{1}, …, f_{n}) \ar@{^{(}->}[r] & V (F_{1}, …, F_{n}) .}

Lemma 4.4 For each i, the embedding V_{i} ↪ \overline{V}_{i} is an isomorphism.

Proof. We have to show that \overline{V}_{i} has no points “at infinity”, that is, the intersection V (Z) ∩ \overline{V}_{i} is trivial. We show in fact the stronger statement that V (Z) ∩ V (F_{1}, …, F_{n}) is trivial.

Let f^{(s)} := σ_{K|k}^{s}(f)(x^{(s)}, y^{(s)}) and let F^{(s)} := F (x^{(s)}, Y^{(s)}, Z) for s = 0, …, n − 1.

Let us consider the isomorphism of graded K-algebras

K[x_{1}, …, x_{n}][Y_{1}, …, Y_{n}, Z] ⟶ K[x^{(1)}, …, x^{(n)}][Y^{(1)}, …, Y^{(n)}, Z]

x^{(s)} ↦ ∑_{j=1}^{n} σ_{K|k}^{s}(b_{j}) · x_{j} , Y^{(s)} ↦ ∑_{j=1}^{n} σ_{K|k}^{s}(b_{j}) · Y_{j} , Z ↦ Z .

We have the following commutative diagram over K:

Spec(K[x_{1}, …, x_{n}])
×
Spec(K[y_{1}, …, y_{n}])

[figure]

Spec(K[x^{(1)}, …, x^{(n)}])

×

Spec(K[y^{(1)}, …, y^{(n)}])

Res_{k}^{K}(E) = V (f_{1}, …, f_{n})_{K}

[figure] [figure]

[figure] [figure]

[figure]

V (f^{(1)}, …, f^{(n)}) = ∏_{s=0}^{n−1} σ_{K|k}^{s}(E_{a})

[figure] [figure]

[figure]

[figure]

V (F_{1}, …, F_{n})_{K} [figure] [figure]

[figure]

V (F^{(1)}, …, F^{(n)}) [figure]

[figure]

Spec(K[x_{1}, …, x_{n}])

×
Proj(K[Y_{1}, …, Y_{n}, Z])

[figure]

Spec(K[x^{(1)}, …, x^{(n)}])

×

Proj(K[Y^{(1)}, …, Y^{(n)}, Z])

Here the horizontal maps are induced by the isomorphism mentioned above. They are clearly isomorphisms. One can easily see that the middle morphism on the right is an isomorphism: We have F (x^{(s)}, Y^{(s)}, 0) = (Y^{(s)})^{2}, and the scheme V ((Y^{(1)})^{2}, …, (Y^{(n)})^{2}, Z) is trivial. Therefore the middle morphism on the left is an isomorphism too. □

Let us fix the following notation: For b ∈ ℕ_{0}, (P_{0})_{⊚}^{b} is the point ((P_{0})_{⊚}, …, (P_{0})_{⊚}) with b entries. Let now for ℓ = 0, …, m the k-scheme V_{ℓ} be the following subscheme of V_{1} × ⋯ × V_{m}:

V_{ℓ} := V_{1} × ⋯ × V_{ℓ} × (P_{0})_{⊚}^{m−ℓ} .

Furthermore, let d_{ℓ} ∈ k[(y_{i′,j′})_{i′=1,...,ℓ,j′=1,...,n}] be the polynomial obtained from d by evaluating y_{i′,j′} for i′ = ℓ + 1, …, m and j′ = 1, …, n at (P_{0})_{⊚}. Note that d_{ℓ} does not vanish identically on V_{ℓ} because it does not vanish at (P_{0})_{⊚}^{ℓ}.

We want to show by induction on ℓ:

#(V_{ℓ} ∩ V (d))(k) ≤ ℓ · n^{4} · 2^{n} · (2q)^{(∑_{i=1}^{ℓ} dim(U_{i}))−1}

Recall here that dim(U_{i}) = dim(V_{i}).

The induction base is ℓ = 0. As d does not vanish at (P_{0})_{⊚}^{ℓ}, the set V_{0} ∩ V (d) is empty. Therefore the claim holds.

So let ℓ ≤ m be given and let us assume that the claim holds for ℓ − 1. The set (V_{ℓ} ∩ V (d))(k) can be divided into two disjoint parts: The first

part consists of the points (P_{1}, …, P_{ℓ}) with d_{ℓ−1}(P_{1}, …, P_{ℓ−1}) = 0. The second part consists of the points (P_{1}, …, P_{ℓ}) with d_{ℓ−1}(P_{1}, …, P_{ℓ−1}) ≠ 0.

We first consider points in the first part. As over each point of 𝔸^{1}(K) there lie at most 2 points of E_{a}(K), over each point 𝔸^{n}(k) lie at most two points of Res_{k}^{K}(E_{a})(k). In particular, over each point of 𝔸_{k}[U_{ℓ}](k) lie at most 2 points of V_{ℓ}(k). Because of this and because of the induction hypothesis, there are

≤ (2q)^{dim(U_{ℓ})} · (ℓ − 1) · n^{4} · 2^{n} · (2q)^{(∑_{i=1}^{ℓ−1} dim(U_{i}))−1}
= (ℓ − 1) · n^{4} · 2^{n} · (2q)^{(∑_{i=1}^{ℓ} dim(U_{i}))−1}

points in the first part.

We now consider points in the second part.

Let (P_{1}, …, P_{ℓ−1}) ∈ V_{1}(k) × ⋯ × V_{ℓ−1}(k) with d_{ℓ−1}(P_{1}, …, P_{ℓ−1}) ≠ 0, that is, d_{ℓ}(P_{1}, …, P_{ℓ−1}, (P_{0})_{⊚}) ≠ 0.

The polynomial

d_{ℓ}(P_{1}, …, P_{ℓ−1}) ∈ k[y_{ℓ,1}, …, y_{ℓ,n}] ⊆ k[x_{ℓ,1}, …, x_{ℓ,dim(U_{ℓ})}, y_{ℓ,1}, …, y_{ℓ,n}]

is now non-trivial on V_{ℓ}. As – by the conditions we have imposed – V_{ℓ} is irreducible, V_{ℓ} ∩ V (d_{ℓ}(P_{1}, …, P_{ℓ−1})) is of codimension 1 in V_{ℓ} by Krull’s Hauptidealsatz, with other words, it is of dimension dim(U_{ℓ}) − 1.

The polynomial d_{ℓ}(P_{1}, …, P_{ℓ−1}) is already homogeneous with respect to y_{ℓ,1}, …, y_{ℓ,n}; let \overline{d} ∈ k[Y_{ℓ,1}, …, Y_{ℓ,n}, Z] ⊆ k[x_{ℓ,1}, …, x_{ℓ,dim(U_{ℓ})}][Y_{ℓ,1}, …, Y_{ℓ,n}, Z] be the polynomial obtained by substituting Y_{ℓ,n} for y_{ℓ,n}. This is a homogeneous polynomial of degree dim(U_{ℓ})·(n−1) with respect to Y_{ℓ,1}, …, Y_{ℓ,n}, Z. As V_{ℓ} = \overline{V}_{ℓ} (Lemma 4.4), we have

V_{ℓ} ∩ V (d_{ℓ}(P_{1}, …, P_{ℓ−1})) = \overline{V}_{ℓ} ∩ V (\overline{d}) =

V (F_{(ℓ),1}, …, F_{(ℓ),n}, \overline{d}) ⊆ Spec(k[x_{ℓ,1}, …, x_{ℓ,dim(U_{ℓ})}]) × Proj(k[Y_{ℓ,1}, …, Y_{ℓ,n}, Z]) .

Let Res = Res(G_{1}, …, G_{n+1}) be the dense multivariate resultant for n+1 homogeneous variables and polynomials of (homogeneous) degrees 2, …, 2, dim(U_{i}) · (n − 1). Here, the G_{1}, …, G_{n+1} are independent generic polynomials, that is, polynomials with algebraically independent coefficients. (As in [Die11b], the similarity between the notation for the Weil restriction and the resultant is accidental.)

By taking the resultant of the system F_{(ℓ),1}, …, F_{(ℓ),n}, \overline{d} with respect to Y_{ℓ,1}, …, Y_{ℓ,n}, Z, we obtain Res(F_{(ℓ),1}, …, F_{(ℓ),n}, \overline{d}), which is a non-trivial polynomial in k[x_{ℓ,1}, …, x_{ℓ,dim(U_{ℓ})}]. For some point Q ∈ 𝔸^{n}(\overline{k}), the resultant Res(F_{(ℓ),1}, …, F_{(ℓ),n}, \overline{d}) vanishes at Q if and only if there is a \overline{k}-rational point in \overline{V}_{ℓ} ∩ V (\overline{d}) = V_{ℓ} ∩ V (d_{ℓ}(P_{1}, …, P_{ℓ−1})) over Q.

We want to determine the multidegree of this polynomial. First we consider the degrees of Res as a polynomial on the coefficients of the G_{j}. By [GKZ94, subsection 3.3 A] we have: For j = 1, …, n, Res is a homogeneous polynomial of degree dim(U_{j}) · (n − 1) · 2^{n−1} < n^{2} · 2^{n−2} in the coefficients of the G_{j}. The inequality is obtained as follows: As m ≥ 2, dim(U_{j}) ≤ ⌈\frac{n}{2}⌉ ≤ \frac{n+1}{2}. Furthermore, Res is a homogeneous polynomial of degree 2^{n} in the coefficients of G_{n+1}. Moreover, F_{(ℓ),j} has degree at most 3 in the x_{ℓ,j′} (j′ = 1, …, dim(U_{i})) and \overline{d} obviously has degree 0 in the x_{ℓ,j′}.

Therefore, Res(F_{ℓ,1}, …, F_{ℓ,n}, \overline{d}) has degree at most n · 3 · n^{2} · 2^{n−2} in each of the variables x_{ℓ,j′}. Its total degree is thus at most 3n^{4} · 2^{n−2}. By Lemma 4.3, the locus the resultant contains at most 3n^{4} ·2^{n−2} ·q^{dim(U_{ℓ})−1} krational points. As over each of these points lie at most two k-rational points of V_{ℓ} ∩ V (d(P_{1}, …, P_{ℓ−1})), this set contains at most 6n^{4} · 2^{n−2} · q^{dim(U_{ℓ})−1} points. We now let P_{1}, …, P_{ℓ−1} vary, and we obtain that there are at most 6n^{4} · 2^{n−2} · q^{dim(U_{ℓ})−1} · (2q)^{∑_{i=1}^{ℓ−1} dim(U_{i})} = 6n^{4} · 2^{n−1} · 2^{∑_{i=1}^{ℓ−1} dim(U_{i})−1} · q^{∑_{i=1}^{ℓ} dim(U_{i})−1} < n^{4} · 2^{n} · (2q)^{(∑_{i=1}^{ℓ} dim(U_{i}))−1} points in the second part of the set (V_{a} ∩ V (d))(k). (We use that dim(U_{ℓ}) ≥ 2 as m ≤ \frac{n}{2}.)

Altogether, there are less than ℓ · n^{4} · 2^{n} · (2q)^{(∑_{i=1}^{ℓ} dim(U_{i}))−1} points in (V_{ℓ} ∩ V (d))(k).

This concludes the proof of Proposition 4.2. □

There are at most 3 K-rational ramification points in E_{a} under x_{|E_{a}}. Therefore, there are at most 3·2^{m−1} ·q^{n−1} < 2^{n} ·q^{n−1} tuples in F_{1} ×⋯×F_{m} which do not satisfy Condition 4.1. Proposition 4.2 gives therefore:

Proposition 4.5 The number of tuples in F_{1}×⋯×F_{m} which do not define isolated decompositions is at most (n^{5} · 4^{n} + 2^{n}) · q^{n−1}.

The case that q is even and j ≠ 0

Let a ∈ K be the ramification point of E_{a} over 𝔸_{K}^{1}. Then \frac{dx_{|E}}{x_{|E}−a} is a holomorphic differential on E.

Proceeding just as above, we obtain a non-trivial polynomial d ∈ k[(x_{i,j})_{i=1,...,m,j=1,...,dim(U_{i})}] of total degree n^{2} − n such that for points (P_{1}, …, P_{m}) ∈ E(K)^{m} with x(P_{i}) ∈ U_{i} satisfying Condition 4.1, ((P_{1})_{⊚}, …, (P_{m})_{⊚}) is an isolated reduced point in its fiber if and only if d((P_{1})_{⊚}, …, (P_{m})_{⊚}) = 0.

There are at most (n^{2}−n)·q^{n−1} points in the locus of d on 𝔸_{k}^{n}. Moreover, over each point of 𝔸^{1}(K) are at most two points of E(K). The number of points (P_{1}, …, P_{m}) ∈ V_{1}(k)×⋯×V_{m}(k) satisfying Condition 4.1 which are not isolated reduced points in their fiber is therefore at most 2^{m} · (n^{2} − n) · q^{n−1}. Therefore:

Proposition 4.6 The number of tuples in F_{1}×⋯×F_{m} which do not define isolated decompositions is at most 2^{m} · n^{2} · q^{n−1}.

The case that q is even and j = 0

In this case, dx_{|E} itself is a holomorphic differential on E. It follows that (τ_{(P_{0}−P_{i})_{⊚}})_{∗}(t_{i,j}((P_{i})_{⊚})) = (t_{i,j}((P_{0})_{⊚})) for any P ∈ E_{a}(K). Therefore, the morphism a′_{m} : V_{1} × ⋯ × V_{m} ⟶ Res_{k}^{K}(E) is unramified everywhere and we obtain:

Proposition 4.7 Every decomposition is isolated.

The final result of the analysis

All in all, we have:

Proposition 4.8 For

• 2^{5n} ≤ q

or

• q even, n^{3} ≤ q and m ≤ ⌈\sqrt{log_{2}(q)}⌉

the following holds: The probability that a uniformly randomly distributed point of E(K) has an isolated decomposition is in

\frac{1}{e^{O(mn)}} = (\frac{1}{e^{mn}} )^{Ω(1)} .

We remark here that the condition m ≤ ⌈\sqrt{log_{2}(q)}⌉ is satisfied for m in the preliminary algorithm presented in the introduction. Proof. Let first q be odd and the first condition satisfied. By the conditions in subsection 2.5, we have #F_{i} ≥ \frac{1}{4} · q^{dim(U_{i})} for all i and therefore #(F_{1} × ⋯ × F_{m}) ≥ \frac{1}{4^{m}} · q^{n} ≥ \frac{1}{4^{n}} · q^{n}. By Proposition 4.5, at most (n^{5} · 4^{n} + 2^{n}) · q^{n−1} of these tuples do not define isolated decompositions. So if n^{5} · 4^{n} + 2^{n} ≤ \frac{1}{2} · \frac{1}{4^{n}} · q, we have at least \frac{1}{2} · \frac{1}{4^{n}} · q^{n} tuples which do define isolated decompositions. This is for example the case if 2^{5n} ≤ q and n is large enough, and for every fixed n it holds if q is large enough. By Proposition 3.3 a) the image of the set of tuples in F_{1}×⋯×F_{m} which define isolated decompositions has a size of \frac{1}{e^{O(mn)}} · q^{n}. The probability that a uniformly randomly distributed point in E(𝔽_{q^{n}}) has an isolated decomposition is therefore in \frac{1}{e^{O(mn)}} .

We now consider the case that q is even. The proof is similar to the previous one, only that we now apply propositions 4.6 and 4.7. We now want that the condition 2^{m} ·n^{2} ≤ \frac{1}{2} · \frac{1}{4^{m}} ·q is satisfied, that is, 2·2^{3m} ·n^{2} ≤ q. This is always satisfied under the first condition, that is, 2^{5n} ≤ q. Furthermore, under the condition that m ≤ ⌈\sqrt{log_{2}(q)}⌉ the desired condition is in particular satisfied if 2n^{2} ≤ 2^{log_{2}(q)−3⌈\sqrt{log_{2}(q)}⌉}. This condition is for example satisfied if n^{3} ≤ q and n is large enough, and it holds for every fixed n if q is large enough. □

Derivation of Theorem 2

Finally, we show how Theorem 2 follows. In addition we show that in characteristic 2 one can obtain a result which on first sight seems to be an improvement over Theorem 2 but is in fact further improved upon by Theorem 3 which relies solely on Theorem 2.

As already mentioned in the outline in the introduction, the basic structure of the index calculus algorithm is the same as that in [Die11b]. So we only discuss the constructions surrounding the definition of the factor base and briefly the relation generation and the linear algebra part, using the results proved above. For an overview over the complete algorithm, we refer to subsection 2.3 of our previous work.

The input to the index calculus algorithm consists of a field extension 𝔽_{q^{n}}|𝔽_{q}, an elliptic curve E/𝔽_{q^{n}} and points A, B ∈ E(𝔽_{q^{n}}) and B ∈ ⟨A⟩ such that 2^{5n} ≤ q or q is even and n^{3} ≤ q. The following considerations hold for q and n large enough. An algorithm for all instances under consideration running in the claimed expected time can be obtained by running the index calculus algorithm “in parallel” with a brute force computation.

Similarly to the “preliminary algorithm”, we set m := min\{⌈\sqrt{log_{2}(q)}⌉, ⌊\frac{n}{2}⌋\}. (We need m ≤ \frac{n}{2} in order to be able to apply the algorithm for the construction of a decomposition of K in subsection 2.5.) So d = ⌈\frac{n}{m}⌉ ≤ max(_{\frac{n}{\sqrt{log_{2}(q)}}} + 1, 3) and thus Poly(q^{d}) ⊆ e^{O(max(log(q),n·\sqrt{log(q)}))}.

The expected running time of the construction of the decomposition of K and the definition of the factor base is in Poly(n·q^{d}) ⊆ e^{O(max(log(q),n·\sqrt{log(q)}))} (see Proposition 2.10). We have an algorithm for the “new decomposition problem” with an expected running time of Poly(e^{mn}·log(q)) ⊆ e^{O(n·\sqrt{log(q)})} and a success probability of \frac{1}{e^{O(mn)}} (see propositions 3.3 and 4.8). Therefore

the expected running time of the relation generation part is in Poly(e^{n·\sqrt{log(q)}}· m · q^{d}) ⊆ e^{O(max(log(q),n·\sqrt{log(q)}))}. The linear algebra part has an expected running time of Poly(m · q^{d}) ⊆ e^{O(max(log(q),n·\sqrt{log(q)}))}.

In total, we obtain an expected running time of

e^{O(max(log(q),n·\sqrt{log(q)}))} .

We recall again that we only considered instances with 2^{5n} ≤ q or q even and n^{3} ≤ q so far. The derivation of Theorem 2 is now analogous to the derivation of Theorem 1 from [Die11b, Proposition 2.11].

We make the following case distinction: If 2^{5n} ≤ q, we apply the index calculus algorithm directly. If 2^{5n} > q, we set a := ⌈\frac{5n}{log_{2}(q)}⌉ and apply the index calculus algorithm to the curve E_{𝔽_{q^{an}}}, the field extension 𝔽_{q^{an}}|𝔽_{q^{a}} and A, B. Now 2^{5n} ≤ q^{a}, thus we can conclude that the index calculus algorithm runs in an expected running time of e^{O(max(log(q^{a}),n·\sqrt{log(q^{a})}))} = e^{O(n^{3/2})}.

This gives Theorem 2 except that in the theorem the field extension 𝔽_{q^{n}}|𝔽_{q} is not given with the input data. As already pointed out in [Die11b], one can apply the above algorithm with all possible field extensions “in parallel” to obtain the desired result.

In addition to the derivation of Theorem 2 we now consider only instances in characteristic 2. Under this condition, we can proceed as follows: For n^{3} ≤ q we apply the index calculus algorithm directly. For n^{3} > q, we set a := ⌈\frac{3 log_{2}(n)}{log_{2}(q)}⌉ and proceed as above. We obtain an expected running time

of e^{O(n·\sqrt{log(n)})}. In total, we obtain an expected running time of

e^{O(max(log(q), n·log(q)^{1/2}, n·log(n)^{1/2}))} ;  (19)

with q = 2^{m} this is

e^{O(max(m, n·m^{1/2}, n·log(n)^{1/2}))} .  (20)

We note however that for the derivation of Theorem 3 we only apply Theorem 2 under the condition that n ≤ m. Under this condition, we do not have an improvement upon the expected time given in Theorem 2, and in fact Theorem 3 improves upon the expected time given by (20) if m ∈ o(n).

References

[CLO05] D. Cox, J. Little, and D. O’Shea. Using Algebraic Geometry. Springer, 2005.

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

[Die11b] C. Diem. On the discrete logarithm problem in elliptic curves. Compos. Math., 147, 2011.

[Ful93] W. Fulton. Introduction to Toric Varieties. Princeton University Press, 1993.

[GKZ94] I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants, and Multidimensional Determinants. Birkäuser, 1994.

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

[Roj99] J.M. Rojas. Solving degenerate sparse polynomial systems faster. J. Symbolic Computation, 28:155–186, 1999.

[Sil86] J. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, 1986.

Appendix: Misprints in the previous work

I would like to take the opportunity to correct two misprints in [Die11b].

• In subsection 4.2 the following situation is considered: Let k be a field, let n_{1} > n_{2}, and let p : (ℙ_{k}^{1})^{n_{1}} = ∏_{i=1}^{n_{1}} Proj(k[X_{i}, Y_{i}]) ⟶ (ℙ_{k}^{1})^{n_{2}} = ∏_{i=1}^{n_{2}} Proj(k[X_{i}, Y_{i}]) be the projection to the first n_{2} factors. Let h_{i} be the class of V (X_{i}) in any of the two Chow rings. Lemma 4.6 is on the push-forward map p_{∗} : CH((ℙ_{k}^{1})^{n_{1}}) ⟶ CH((ℙ_{k}^{1})^{n_{2}}), which is a group homomorphism. There is a misprint in the lemma. The correct statement is:

Let \underline{e} ∈ \{0, 1\}^{n_{1}}. Then p_{∗}(h_{1}^{e_{1}} ⋯ h_{n_{1}}^{e_{1}}) = h_{1}^{e_{1}} ⋯ h_{n_{2}}^{e_{2}} (rather than being 1) if e_{n_{2}+1} = ⋯ = e_{n_{1}} = 1 and p_{∗}(h_{1}^{e_{1}} ⋯ h_{n_{1}}^{e_{1}}) = 0 otherwise.

Computations with the push-forward map are used only once in the analysis of the algorithm, namely in equalities (6) in subsection 4.5. Here, the correct statement is applied.

• In Proposition 4.28 a subset M of {(P_{1}, …, P_{n}) ∈ E(K)^{n} | ∀i = 1, …, n : φ(P_{i}) ∈ ℙ^{1}(k)} is fixed and a lower bound on the number of elements P ∈ E(K) such that there exists a φ-isolated decomposition (P_{1}, …, P_{n}) of P or −P with P_{1}, …, P_{n} ∈ M is given. This lower bound is a difference, and in the subtrahend a factor of n! is missing. The correct lower bound is:

\frac{#M − n^{3} · n! · 2^{2n^{2}−n} · (q + 1)^{n−1}}{n! · 2^{n^{2}}}

In a similar way, the next lower bound is also incorrect. All following bounds are correct again and no further changes have to be performed for the proof of Proposition 4.29. Proposition 4.28 is also cited for Proposition 5.9 in [Die11a], which is concerned with an application for fixed n. This proposition is not at all affected by the cited misprint.