On the discrete logarithm problem in elliptic curves

Claus Diem

August 9, 2010

Dedicated to Gerhard Frey

Abstract We study the elliptic curve discrete logarithm problem over finite

extension fields. We show that for any sequences of prime powers (q_{i})_{i∈ℕ} and natural numbers (n_{i})_{i∈ℕ} with n_{i} ⟶ ∞ and \frac{n_{i}}{log(q_{i})} ⟶ 0 for i ⟶ ∞, the elliptic curve discrete logarithm problem restricted to curves over the fields 𝔽_{q_{i}^{n_{i}}} can be solved in subexponential expected time (q_{i}^{n_{i}})^{o(1)}. We also show that there exists a sequence of prime powers (q_{i})_{i∈ℕ} such that the problem restricted to curves over 𝔽_{q_{i}} can be solved in an expected time of e^{O(log(q_{i})^{2/3})}.

Contents

1 Introduction 2

2 The key algorithms 7 2.1 The decomposition algorithm . . . . . . . . . . . . . . . . . . 7 2.2 Computing a suitable covering . . . . . . . . . . . . . . . . . 11 2.3 The index calculus algorithm . . . . . . . . . . . . . . . . . . 12

3 The summation polynomials 16

4 Geometric background on the algorithm and analysis 21 4.1 Weil restrictions . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Intersection theory in (ℙ_{k}^{1})^{n} . . . . . . . . . . . . . . . . . . . 24 4.3 Background on the factor base . . . . . . . . . . . . . . . . . 26 4.4 The role of the summation polynomials . . . . . . . . . . . . 29 4.5 Determination of non-zero-dimensional fibers . . . . . . . . . 34

References 40

1 Introduction

The classical discrete logarithm problem in finite prime fields can be solved in an expected time which is subexponential in the bit-length of the group size via the so-called index calculus method. In contrast, it is not known if the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields (the elliptic curve discrete logarithm problem for short) can be solved in subexponential expected time (in the bit-length of the group size). While some infinite classes of elliptic curves are known for which the problem can be solved in subexponential expected time (for example supersingular elliptic curves over prime fields), it was up to now not known if there exists a sequence of finite fields of increasing size such that the problem restricted to curves over these fields can be solved in subexponential expected time.

We prove that such a sequence of finite fields exists. Indeed, we establish the following results. Here and in the following, q is always a prime power and n a natural number.

1. Let sequences of prime powers (q_{i})_{i∈ℕ} and natural numbers (n_{i})_{i∈ℕ} with n_{i} ⟶ ∞ and \frac{n_{i}}{log(q_{i})} ⟶ 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β} = \frac{1}{2} · (\frac{1}{β} − 1) ∈ (0, \frac{1}{2}] and γ := \frac{2β}{β + 1} = 2 · (1 − \frac{1}{β + 1}) < 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})^{γ})} .

3. Let positive real numbers a < b be fixed. Then the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields 𝔽_{q^{n}} with

a · \sqrt{log(q)} ≤ n ≤ b · \sqrt{log(q)}

can be solved in an expected time of

e^{O(log(q^{n})^{2/3})} .

Note that in Result 2, γ as a function of β is strictly monotonically increasing from \frac{2}{3} for β = \frac{1}{2} to 1 in the limit, and α is strictly monotonically decreasing from \frac{1}{2} to 0 in the limit. Result 3 is a special case of Result 2 for α = β = \frac{1}{2}.

Our main result is the following theorem.

Theorem 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}))} .

We note that all results in this work hold for all specified instances; the averaging only takes place on the running times for a fixed input, and there is no averaging over input classes.

Given the Theorem, it is easy to establish Results 1 and 2 (and therefore also Result 3) above. Result 1 follows immediately, and a proof of Result 2 is as follows:

Let α, β, γ and a, b as in Result 2 be given. Note that β = \frac{1}{2α+1} and γ = \frac{1}{α+1}. Now first, as a · log(q)^{α} ≤ n, log(q) = log(q)^{γ·(α+1)} ≤ (\frac{1}{a} · log(q) · n)^{γ} =

\frac{1}{a^{γ}} ·(log(q^{n}))^{γ}. Second, as n ≤ b·log(q)^{β}, n^{2} = n^{γ·(1+ \frac{1}{β})} ≤ (n·b^{\frac{1}{β}} ·log(q))^{γ} = b^{\frac{γ}{β}} · (log(q^{n}))^{γ}.

The method: Index calculus

Index calculus is originally a method to compute discrete logarithms (or indices in the classical terminology) in the multiplicative groups of finite prime fields. It can briefly be described as follows:

Let a prime p and a, b ∈ 𝔽_{p}^{∗}, where a is a generating element, be given. The task is to compute the discrete logarithm of b with respect to a, that is, the smallest number x ∈ ℕ_{0} with a^{x} = b. For this, one first fixes a so-called smoothness bound S ∈ ℕ and considers the set of all prime numbers ≤ S; this set is called the factor base. Then one searches for relations between input elements and classes mod p of factor base elements. After one has obtained enough relations, one derives the discrete logarithm by linear algebra.

A similar method can also be used to compute discrete logarithms in other finite groups: If one considers the multiplicative groups of finite fields of a fixed characteristic, one substitutes prime numbers by irreducible polynomials whose degree is below a certain bound. If one considers the degree 0 class groups of curves over a fixed finite field, one proceeds similarly, substituting polynomials by effective divisors and irreducible polynomials by prime divisors.

It is common to use the term index calculus to refer to the general method of computing discrete logarithms by relation generation and linear algebra. The algorithm for the Theorem is also based on this method. However, in contrast to the algorithms mentioned above, the factor base is defined in an algebraic rather than an arithmetic way, in particular, there is no smoothness bound. Relations are derived by solving systems of multivariate polynomial equations over 𝔽_{q}.

On the proof

We give here a very brief overview of the algorithm leading to the Theorem above.

Let E/𝔽_{q^{n}} be an elliptic curve. Then we compute a covering φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} of degree 2 which satisfies φ ∘ [−1] = φ as well as a certain additional condition (Condition 2.7). The factor base is then given by

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

The relation generation relies on an algorithm which we call decomposition algorithm. Given an elliptic curve E/𝔽_{q^{n}} the extension degree n, a covering φ as above and some point P ∈ E(𝔽_{q^{n}}), this algorithm either fails or outputs tuples (P_{1}, …, P_{n}) ∈ E(𝔽_{q^{n}})^{n} with φ(P_{i}) ∈ ℙ^{1}(𝔽_{q}) for i = 1, …, n such that

P_{1} + ⋯ + P_{n} = P .

The decomposition algorithm is based on solving multivariate systems of polynomial equations over 𝔽_{q}. Of course it fails if there is no such tuple (P_{1}, …, P_{n}). But it might also fail if the algebraic set defined by the associated multivariate system is not zero-dimensional. We remark here that the most difficult part of the proof is to show that for a uniformly distributed point P ∈ E(𝔽_{q^{n}}) with a sufficiently high probability the algebraic set defined by the associated multivariate system is indeed zero-dimensional. In order to prove this result, we pass to higher-dimensional schemes over 𝔽_{q} by using Weil restrictions. The proof then relies crucially on intersection theory in products of projective lines.

Some historical comments

In 2004 I. Semaev put a preprint on the archive of the International Association for Cryptographic Research (IACR) in which he discussed the possibility of index calculus in the groups of rational points on elliptic curves over prime fields ([Sem04]). In his work, Semaev defined the factor base via an upper bound on the x-coordinates of points, where the elliptic curve is given by a Weierstraß model.

He also introduced so-called summation polynomials: Let E be an elliptic curve over a field K, given by a Weierstraß model, and let m ∈ ℕ, m ≥ 2. Let \overline{K} be an algebraic closure of K. Then the m-th summation polynomial as defined by Semaev is an irreducible polynomial f ∈ K[x_{1}, …, x_{m}] such that the following holds: Given P_{1}, …, P_{m} ∈ E(\overline{K}) − \{O\}, we have

f(x(P_{1}), …, x(P_{m})) = 0 ⟷ ∃ϵ_{1}, …, ϵ_{m} ∈ {1, −1} : ϵ_{1}P_{1}+⋯+ϵ_{m}P_{m} = O ,

where we identify 𝔸^{1}(\overline{K}) = ℙ^{1}(\overline{K}) − \{∞\} with \overline{K}. These summation polynomials have degree 2^{m−2} in each variable.

Now, any algorithm to determine solutions with “small coordinates” for multivariate equations of high degree would give rise to an algorithm for relation generation. However, no efficient algorithm for this task is known (except for very special equations), and therefore, Semaev’s approach does (currently) not lead to an algorithm which is faster than generic algorithms to solve discrete logarithm problems.

Semaev’s work lead both P. Gaudry and the author to reflect on the question whether a similar approach over extension fields might not give algorithms which asymptotically are faster than generic algorithms for certain input classes.

In [Gau09] Gaudry argues on a heuristic basis that for any fixed extension degree n ≥ 2 and q ⟶ ∞, the elliptic curve discrete logarithm problem over fields 𝔽_{q^{n}} can be solved in an expected time of

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

on a randomized random access machine.^{1} The author on the other hand tried if a common variation of n and q would lead to a sequence of finite fields such that the elliptic curve discrete logarithm problem over these fields would becomes subexponential, and this study finally lead to the present work.

We note that all previous results on classes of elliptic curves for which the discrete logarithm problem can be solved in subexponential expected time rely on a transfer: First a homomorphism from the group under consideration to another group is applied and then the problem is solved in the second group.

This contrasts to the direct application of index calculus in the groups of rational points of elliptic curves in [Gau09] and the present work. We note that one might argue that we implicitly use the isomorphism E(𝔽_{q^{n}}) ≃ Res_{𝔽_{q}}^{𝔽_{q^{n}}}(E)(𝔽_{q}), where Res_{𝔽_{q}}^{𝔽_{q^{n}}}(E) is the Weil restriction of the elliptic curve E/𝔽_{q^{n}} with respect to 𝔽_{q^{n}}|𝔽_{q}. The important aspect is here nonetheless that no computation is performed in doing so. Weil restrictions are of crucial importance for the analysis of the algorithm, but the algorithm itself can be formulated without even mentioning Weil restrictions, and we do so.

1Using a suitable variant of Gaudry’s algorithm and techniques of the present work, a proof of this result is given in [Die09].

An outline

Let us give an outline of the rest of this article:

In the next section, we give the algorithm for the Theorem above. For this we start off with a “decomposition algorithm” followed by the computation of a suitable covering φ and finally the index calculus algorithm for the Theorem. In Section 3 we introduce homogeneous summation polynomials via a geometric approach. In the last section we give some geometric background on the decomposition algorithm and its analysis.

Notation and Terminology

We set ℕ := {1, 2, 3, …} and ℕ_{0} := {0, 1, 2, …}.

An algebraic closure of a field k is denoted by \overline{k}. If R is a ring with an ideal I and a ∈ R, the residue class of a in R/I is denoted by [a]_{I}. If I = (r), we also use the notation [a]_{r}.

If X and Y are two subschemes of a scheme Z, then we set X ∩ Y := X ×_{Z} Y, the scheme theoretic intersection.

Let now X and Y be locally noetherian schemes. Then a finite and flat morphism X ⟶ Y is also called a flat covering.

Products of projective lines play an important role in this work. We set ℙ^{1} := Proj(ℤ[X, Y]) and x := \frac{X}{Y}. We identify (ℙ^{1})^{n} componentwise with Proj(ℤ[X_{1}, Y_{1}]) × ⋯ × Proj(ℤ[X_{n}, Y_{n}]). Therefore we have bases X_{i}, Y_{i} ∈ Γ((ℙ^{1})^{n}, O(0, …, 0, 1, 0, …, 0)), where the 1 is at the i^{th} position. For any commutative ring A we have the multigraded homogeneous coordinate ring A[X_{1}, Y_{1}, …, X_{n}, Y_{n}] of (ℙ_{A}^{1})^{n}. In the following by a multihomogeneous polynomial in A[X_{1}, Y_{1}, …, X_{n}, Y_{n}] we mean a polynomial which is homogeneous with respect to the multigrading. A multihomogeneous ideal in A[X_{1}, Y_{1}, …, X_{n}, Y_{n}] is then an ideal in A[X_{1}, Y_{1}, …, X_{n}, Y_{n}] which is generated by multihomogeneous polynomials. Now for some multihomogeneous ideal I, we denote the subscheme defined by I in (ℙ_{k}^{1})^{n} by V (I). Moreover, we set x_{i} := \frac{X_{i}}{Y_{i}} and 𝔸^{n} := Spec(ℤ[x_{1}, …, x_{n}]).

Additionally, we set ℙ^{2} := Proj(ℤ[X, Y, Z]) and x := \frac{X}{Z}, y := \frac{Y}{Z}. The elliptic curve E/𝔽_{q^{n}} under consideration is always given by a Weierstraß model in ℙ_{𝔽_{q^{n}}}^{2}.

Finally, let f be a partial function from ℕ to ℝ which is defined on an infinite subset S of ℕ such that f is eventually positive. Then we define the usual sets O(f) and Õ(f) of functions S ⟶ ℝ. Additionally, we define the set of functions which are polynomially bounded in f as

Poly(f) := {g : S ⟶ ℝ : ∃c > 0, N ∈ ℕ : |g(n)| ≤ f(n)^{c} for all n ∈ S with n ≥ N} .

We do not use the usual “Landau-style notation” g = O(f) etc. but g ∈ O(f) instead.

Sets O(f) etc. occur frequently in statements on (expected) running times. We then implicitly fix a (reasonable) representation of the mathematical objects in question (e.g. elliptic curves etc.) by bit-strings, as usual.

Acknowledgments

I thank Steven Galbraith, Pierrick Gaudry, Éric Schost, Nicolas Thériault, and the anonymous referees for their helpful comments.

2 The key algorithms

In this section we outline the algorithm for the Theorem.

2.1 The decomposition algorithm

The decomposition algorithm relies on “homogeneous summation polynomials”. These polynomials can be obtained by homogenizing the summation polynomials introduced by Semaev in [Sem04] in an appropriate way. A more systematic point of view is however to regard Semaev’s summation polynomials as being obtained by dehomogenization of the homogeneous summation polynomials. The homogeneous summation polynomials are studied in detail in Section 3; here we merely mention the key results which are needed to describe the decomposition algorithm.

In Section 3 we show the following two propositions.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

We now outline such an algorithm. The basis is the following proposition.

Proposition 2.5

a) Let k be a field, and let F_{1}, …, F_{n} ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}] be multigraded polynomials of multidegree (d, d, …, d) for some d ∈ ℕ. Then “with multiplicities”, there are ≤ n! · d^{n} isolated points in V (F_{1}, …, F_{n}). Or with other words: The degree of the degree 0 part of the cycle defined by V (F_{1}, …, F_{n}) is ≤ n! · d^{n}. Equality holds if and only if the scheme is 0-dimensional.

b) There exists a randomized algorithm with the following specification: Given a system of multihomogeneous polynomials F_{1}, …, F_{n} ∈ 𝔽_{q}[X_{1}, Y_{1}, …, X_{n}, Y_{n}] of multidegree (d, d, …, d) for some d ∈ ℕ and prime power q, the algorithm outputs a list of 𝔽_{q}-rational points of V (F_{1}, …, F_{ℓ}) containing all 𝔽_{q}-rational isolated points. Moreover, the expected running time is in Poly(n! · d^{n} · log(q)), and the list has a size of Poly(n! · d^{n}).

Sketch of a proof. Part a) follows from intersection theory in (ℙ_{k}^{1})^{n}. For background information, we give a more general statement in subsection 4.2 (Lemma 4.7).

The computational statement can be obtained via an algorithm by Rojas ([Roj99]) and the factorization of a univariate polynomial. This algorithm relies on “twisted Chow forms” or – as one might also say – on U-resultants of toric deformations. We note here that the use of twisted Chow forms for polynomial system solving was pioneered by Canny ([Can90]).

Let k = 𝔽_{q}, and let (𝔾_{m})_{k} = 𝔸_{k}^{1} − {0} be the 1-dimensional standard torus over k. Then given F_{1}, …, F_{n} as above, with the algorithm by Rojas and the factorization of a univariate polynomial, one can obtain a list of 𝔽_{q}- rational points of V (F_{1}, …, F_{ℓ})∩((𝔾_{m})_{k})^{n} containing all 𝔽_{q}-rational isolated points. The expected running time is in Poly(n! · d^{n} · log(q)), and the list has size ≤ n! · d^{n}.

Now ℙ_{k}^{1} can be covered by two copies of (𝔾_{m})_{k}. Therefore by applying Rojas’ algorithm 2^{n}-times with different coordinates on the ℙ_{k}^{1}’s one can obtain a list of points which contains all 𝔽_{q}-rational points. □

We then have the following decomposition algorithm.

We have already remarked that one can compute the polynomial S_{φ,n+1} in an expected time of Poly(e^{n^{2}} · log(q)). Thus one can also determine the polynomials S^{(1)}, …, S^{(n)} in an expected time of Poly(e^{n^{2}} ·log(q)). We then apply an algorithm as in the previous proposition. (As the polynomials are symmetric, we only have to apply Rojas’ algorithm n instead of 2^{n} times.) Let L be the list output by this algorithm.

We now want to find all tuples (P_{1}, …, P_{n}) ∈ E(𝔽_{q^{n}})^{n} with φ(P_{i}) ∈ ℙ^{1}(𝔽_{q}) for all i = 1, …, n and P_{1} + ⋯ + P_{n} = P. For this we iterate over entries of L. For each such entry (Q_{1}, …, Q_{n}) we consider all possibles tuples (P_{1}, …, P_{n}) ∈ E(𝔽_{q^{n}})^{n} with φ(P_{i}) = Q_{i} for i = 1, …, n and check if P_{1} + ⋯ + P_{n} = P. We output all tuples (P_{1}, …, P_{n}) for which this is the case.

Now for each tuple (Q_{1}, …, Q_{n}) ∈ L we need Õ(2^{n}) · Poly(log(q)) bit operations, and we have Poly(e^{n^{2}}) such tuples (Q_{1}, …, Q_{n}). The expected total running time is then still in Poly(e^{n^{2}} · log(q)).

We obtain:

Proposition 2.6 There exists a decomposition algorithm which operates in an expected time of Poly(e^{n^{2}} · log(q)).

In order to analyze the index calculus algorithm we need a lower bound on the probability that a uniformly randomly distributed point has a φisolated decomposition. In order to derive such a lower bound, we need the following condition on the covering φ:

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

Here and in the following σ is the relative Frobenius automorphism of \overline{k}|k.

In the next subsection we prove:

Proposition 2.8 Given a prime power q, n ∈ ℕ and an elliptic curve over 𝔽_{q^{n}} in Weierstraß form such that (q, n) ≠ (3, 2) one can compute a covering φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} of degree 2 with φ ∘ [−1] = φ satisfying Condition 2.7 in an expected time of Poly(n · log(q)).

The key result for the analysis of the algorithm for the Theorem is now as follows:

Proposition 2.9 Let ϵ > 0. Then for n large enough^{2} and (2 + ϵ) · n^{2} ≤ log_{2}(q) the following holds: Let E/𝔽_{q^{n}} be an elliptic curve, and let φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} be a covering of degree 2 with φ ∘ [−1] = φ such that Condition 2.7 is satisfied.

2As usual, by the phrase “for n large enough” we mean that there exists a constant C > 0 such that the statement holds for n ≥ C.

Then the probability that a uniformly distributed point of E(𝔽_{q^{n}}) has a φ-isolated decomposition is ≥ q^{− \frac{1}{2}} .

Section 4 is devoted to the proof of this proposition.

2.2 Computing a suitable covering

We discuss how a covering φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} satisfying Condition 2.7 can be computed efficiently.

We make some case distinctions. In each case we start off with a specific Weierstraß model and determine some automorphism α of ℙ_{𝔽_{q^{n}}}^{1}. Then we set φ := α ∘ x_{|E}.

2.2.1 Even characteristic

Let first j(E) = 0. Then by an easy coordinate change the “affine part” of E is defined by a polynomial

y^{2} + a_{3}y + x^{3} + a_{4}x + a_{6} .

(see [Sil86, Appendix A]) (with a_{3} ≠ 0). Now x_{|E} is ramified exactly over ∞. We set α := \frac{ax−1}{x} for some a ∈ 𝔽_{q^{n}} which is not contained in any proper subfield of 𝔽_{q^{n}}|𝔽_{q}.^{3} Then α maps ∞ to a, and thus φ is ramified exactly at a. Clearly the condition is satisfied.

Let now j(E) ≠ 0. Then wlog. E the “affine part” of E is defined by the polynomial

y^{2} + xy + x^{3} + a_{2}x^{2} + a_{6} .

Then x_{|E} is ramified exactly over 0 and ∞. We set α := x + a with a as above. Then φ is ramified at a and ∞, and again the condition is satisfied.

2.2.2 Odd characteristic

Now wlog. E is defined by

y^{2} − f(x) ,

where f(x) ∈ 𝔽_{q^{n}}[x] is monic of degree 3. The conditions which have to be satisfied are now more subtle but the algorithm is very simple:

3By a “proper subfield” we mean here a subfield of a field extension K|k which is not equal to K.

We choose λ ∈ 𝔽_{q^{n}} uniformly at random and with α := x − λ we check if the condition is satisfied. We repeat this until the condition is satisfied.

Note here that if f(x) = (x − λ_{1})(x − λ_{2})(x − λ_{3}) (with λ_{i} ∈ 𝔽_{q^{6n}}), then the ramification points of φ = α ∘ x_{|E} in ℙ^{1}(\overline{𝔽}_{q}) are λ_{i} − λ for i = 1, 2, 3. So it is easy to check the condition.

Proposition 2.8 now follows from the following lemma. (Note that we only apply the lemma in the case that q is odd.)

Lemma 2.10 There exists a constant C ∈ (0, 1) such that the following holds:

Let q be a prime power and n a natural number such that (q, n) ≠ \{(2, 2), (3, 2), (2, 3), (2, 4)\}. Now let λ_{1}, λ_{2}, λ_{3} ∈ \overline{𝔽}_{q}, and let λ be a uniformly distributed element in 𝔽_{q^{n}}. Then with a probability ≥ C we have

(λ_{1} − λ)^{q^{i}} ∉ {λ_{1} − λ, λ_{2} − λ, λ_{3} − λ}

for i = 1, …, n − 1.

Proof. Let ℓ = 1, 2, 3. We have (λ_{1} − λ)^{q^{i}} = λ_{ℓ} − λ if and only if λ^{q^{i}} − λ = λ_{1}^{q^{i}} − λ_{ℓ}. The map 𝔽_{q^{n}} ⟶ 𝔽_{q^{n}} , λ ↦ λ^{q^{i}} − λ is an 𝔽_{q}-linear map with kernel 𝔽_{q^{gcd(i,n)}}. There are thus either no or q^{gcd(i,n)} such λ.

We obtain: In total there are at most 3 ∑_{i=1}^{n−1} q^{gcd(i,n)} elements λ for which the condition in the lemma is not satisfied.

Now 3 ∑_{i=1}^{n−1} q^{gcd(i,n)} ≤ 3(n − 1) · q^{n/2}, and therefore the probability in question is

≥ 1 − \frac{3(n − 1)}{q^{n/2}} ≥ 1 − \frac{3(n − 1)}{2^{n/2}} .

For n ≥ 10 this is ≥ \frac{5}{32} > 0.

One also easily sees that for n ≤ 9 and (q, n) ≠ {(2, 2), (3, 2), (2, 3), (2, 4)} the probability is positive. □

2.3 The index calculus algorithm

Below we give an algorithm which leads to the following result.

Proposition 2.11 Let ϵ > 0. Then there exists a randomized algorithm with the following specification: Given a prime power q, a natural number n with (2 + ϵ) · n^{2} ≤ log_{2}(q), an elliptic curve E over 𝔽_{q^{n}} (in Weierstraß form) and two points A, B ∈ E(𝔽_{q^{n}}) with B ∈ ⟨A⟩, it outputs the discrete logarithm of B with respect to A. Moreover, the expected running time is polynomially bounded in q.

This proposition implies the Theorem:

Let an instance consisting of a prime power q, a natural number n, an elliptic curve E over 𝔽_{q^{n}} and two points A, B ∈ E(𝔽_{q^{n}}) with B ∈ ⟨A⟩ be given.

We then proceed with a case distinction:

If 3 · n^{2} ≤ log_{2}(q), we apply an algorithm for Proposition 2.11. Thus for these instances we obtain an expected running time which is polynomially bounded in q = e^{log(q)}.

If on the other hand 3 · n^{2} > log_{2}(q), we set m := ⌈\frac{3·n^{2}}{log_{2}(q)}⌉. Note that 3 · n^{2} ≤ log_{2}(q^{m}) and m ≤ \frac{6·n^{2}}{log_{2}(q)}. We then apply an algorithm for Proposition 2.11 to the instance consisting of the prime power q^{m}, the natural number n, the elliptic curve E_{𝔽_{q^{mn}}} over 𝔽_{q^{mn}} and A, B ∈ E(𝔽_{q^{mn}}). Thus for these instances the expected running time is then polynomially bounded in q^{m} ≤

q^{\frac{6·n^{2}}{log_{2}(q)}} = 2^{6n^{2}} ∈ Poly(e^{n^{2}}).

In the Theorem, only q^{n} but not q and n is part of the input. We can then apply the algorithm just outlined for all possible extension degrees “in parallel”. The claimed expected running time still holds. □

We now outline an algorithm for Proposition 2.11. For any ϵ > 0, the algorithm below computes the discrete logarithm in any expected time of Poly(q) provided that n is large enough. Proposition 2.11 can then be obtained by applying this algorithm “in parallel” with a brute force computation.

The algorithm

Input: A prime power q, a natural number n with (q, n) ≠ (3, 2), an elliptic curve E over 𝔽_{q^{n}} in Weierstraß form, A, B ∈ E(𝔽_{q^{n}}) with B ∈ ⟨A⟩.

Output: The discrete logarithm of B with respect to A.

1. Compute N ⟵ #E(𝔽_{q^{n}}).

2. Compute the factorization of N.

3. Compute a generating system C_{1}, C_{2} of E(𝔽_{q^{n}}).

4. Choose a covering φ : E ⟶ ℙ_{𝔽_{q^{n}}}^{1} of degree 2 with φ∘[−1] = φ satisfying Condition 2.7.

5. Construct the factor base F = {F_{1}, F_{2}, …, F_{k}}, that is, enumerate the set {P ∈ E(𝔽_{q^{n}}) | φ(P) ∈ ℙ^{1}(𝔽_{q})}.

6. Construct matrices R ∈ (ℤ/Nℤ)^{(k+3)×k} and S ∈ (ℤ/Nℤ)^{(k+3)×2} as well as vectors \underline{α}, \underline{β} ∈ (ℤ/Nℤ)^{k+3} as follows:

For i = 1, …, k + 3 do

Repeat Choose uniformly and independently randomly α, β, s_{1}, s_{2} ∈ ℤ/Nℤ and apply a decomposition algorithm to s_{1}C_{1} + s_{2}C_{2} + αA + βB.

Until a decomposition is obtained. Choose such a decomposition and let

∑_{j} r_{i,j}F_{j} = s_{i,1}C_{1} + s_{i,2}C_{2} + α_{i}A + β_{i}B

be the relation generated.

7. Compute a lower row echelon form H of (R|S) (over ℤ/Nℤ); apply the row transformations also to \underline{α}, \underline{β}; let \underline{α}′, \underline{β}′ be the resulting vectors.

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

9. Compute ord(A), using the factorization of N.

10. Output the unique non-negative number x ∈ {0, …, ord(A) − 1} with [x]_{ord(A)} = [ξ]_{ord(A)} ∈ ℤ/ ord(A)ℤ.

For the correctness of the algorithm note that as (R|S) is a (k + 3) × (k + 2)-matrix, the first row of H is trivial. Therefore we have the relation α′_{1}A + β′_{1}B = 0.

We now give some additional information on subroutines for the various steps of the algorithm and their complexity.

Step 1 can be performed in polynomial time with Schoof’s algorithm ([Sch85]).

Step 2 can be performed in an expected time of Poly(e^{(log(N)·log(log(N)))^{1/2}}), for example with the algorithm by Lenstra and Pomerance ([LP92]).

Step 3 can be performed in expected polynomially bounded time with an algorithm by Miller ([Mil04]). Briefly, one chooses two points uniformly at random and checks whether they form a generating system by computing the Weil pairing of the two points. For the claimed expected running time, one needs the factorization of N.

As already proven above, for (q, n) ≠ (3, 2), Step 4 can be performed in expected polynomially bounded time.

In Step 5, the factor base clearly has ≤ 2(q+1) elements and can therefore be constructed in an expected time of Poly(n · log(q)) · q.

Step 9 can be performed in polynomial time along the following lines: As in the algorithm, let N = ∏_{i=1}^{v} ℓ_{i}^{e_{i}} with e_{i} ∈ ℕ and pairwise distinct

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

We now discuss steps 6, 7 and 8.

Step 6 – Relation generation

As stated, we choose α, β, s_{1}, s_{2} ∈ {0, …, #E(𝔽_{q^{n}})−1} uniformly at random and compute s_{1}C_{1} + s_{2}C_{2} + αA + βB. Then we apply the decomposition algorithm as described in the previous subsection to this element and the covering φ.

We repeat this procedure until the decomposition algorithm outputs at least one decomposition of s_{1}C_{1} + s_{2}C_{2} + αA + βB. Then we choose such a decomposition in such a way that the choice depends only on the element s_{1}C_{1}+s_{2}C_{2}+αA+βB and not on the further internal state of the algorithm.

The time to compute s_{1}C_{1}+s_{2}C_{2}+αA+βB is polynomial in log(q^{n}). By Proposition 2.6, the expected running time of one iteration in the Repeatloop is then in Poly(e^{n^{2}} ·log(q)). Note that for each iteration of the Repeatloop the element s_{1}C_{1} + s_{2}C_{2} + αA + βB is uniformly randomly distributed (and independent of previous choices). Therefore by Proposition 2.9 for instances with (2+ϵ)·n^{2} ≤ log_{2}(q) and n large enough the expected number of iterations in the Repeat-loop is in O(q^{1/2}).

We conclude that for instances with (2 + ϵ) · n^{2} ≤ log_{2}(q) and n large enough, the expected running time of Step 3 is in Poly(e^{n^{2}} ·log(q))·O(q^{1/2})· O(q) ⊆ Poly(q).

Step 7 – Linear algebra

The computation of a lower row echelon form can be performed with an easy modification of the usual Gaußian reduction algorithm with gcd computations. Given a matrix of size m × n over ℤ/Nℤ, the computation can be performed in a time which is polynomially bounded in m · n · log(N).

By the definition of the factor base, we have k + 2 ∈ O(q). We therefore have a running time which is polynomially bounded in q · log(N).

Step 8 – Invertibility

We need to estimate the probability that β′_{1} is invertible. The key result is:

Proposition 2.12 Conditionally to any outcome of Step 5 of the algorithm, the random element β′_{1} is uniformly randomly distributed in ℤ/Nℤ.

For N ⟶ ∞, we have \frac{ϕ(N)}{N} ∈ Ω(\frac{1}{log log(N)}) (cf. [RS62, Formula 3.41]). Therefore, the expected number of iterations of steps 6,7,8 is in O(log log(N)) = O(log log(q)).

Proof of Proposition 2.12. We fix any outcome of Step 5 of the algorithm. Now for each i, β_{i} is stochastically independent of α_{i}A + β_{i}B. Therefore β_{i} is stochastically independent of the i^{th} row of (R|S). It follows that \underline{β} is independent of (R|S). Let U be the transformation matrix such that H = U(R|S); this is also a random variable. Now U is stochastically independent of \underline{β}. Let \underline{u} be the first row of U and note that [\underline{u}]_{ℓ} ≠ \underline{0} for all prime divisors ℓ of N. Then β′_{1} = \underline{u}\underline{β}. Now the statement follows with the following well known lemma. □

Lemma 2.13 Let N be a natural number, and let \underline{u} ∈ (ℤ/Nℤ)^{m} with [\underline{u}]_{ℓ} ≠ \underline{0} for all prime divisors ℓ of N. Furthermore, let \underline{v} be a uniformly distributed random element in (ℤ/Nℤ)^{m}. Then ∑_{i} u_{i}v_{i} is uniformly distributed in ℤ/Nℤ.

Proof. Let us first consider the case that N is a prime power. Then at least one entry of \underline{u} is invertible. This implies the statement. The general case follows then easily with the Chinese Remainder Theorem. □

The overall running time

Altogether we conclude:

We again restrict ourselves to instances with (2 + ϵ) · n^{2} ≤ log_{2}(q). As the factor base has a size of O(q), it is now clear that for n large enough the expected running time of the whole algorithm is then polynomially bounded in q.

3 The summation polynomials

In this section we prove Propositions 2.1 and 2.3 on the summation polynomials. Let E be an elliptic curve over a field k, let m ∈ ℕ, m ≥ 2, and let φ : E ⟶ ℙ_{k}^{1} be a covering of degree 2 which satisfies φ ∘ [−1] = φ.

Now let N_{m} (or N) be the kernel of the addition map E^{m} ⟶ E, (P_{1}, …, P_{m}) ↦ P_{1} + ⋯ + P_{m}. (Here the P_{i} are Z-valued points for some kscheme Z.) Note that N is isomorphic to E^{m−1} via the projection (P_{1}, …, P_{m}) ↦ (P_{1}, …, P_{m−1}).

We now consider the projection E^{m} ⟶ (ℙ_{k}^{1})^{m} induced by φ. Note that [−1] operates on N, and the map N ↪ E^{m} ⟶ (ℙ_{k}^{1})^{m} factors through the quotient N/[−1].

Definition 3.1 Let H_{φ,m} (or H_{m} or H) be the image of N in (ℙ_{k}^{1})^{m} (with the induced subscheme structure).

Proposition 3.2

a) The induced map N/[−1] ⟶ H is finite and birational.

b) H is a hypersurface in (ℙ_{k}^{1})^{m} of multidegree (2^{m−2}, …, 2^{m−2}).

c) The projections H ⟶ ℙ_{K}^{m−1} to any m − 1 of the m components are flat coverings of degree 2^{m−2}.

Proof. The maps N ↪ E^{m} ⟶ (ℙ_{k}^{1})^{m} and H ↪ (ℙ_{k}^{1})^{m} are clearly finite. It follows immediately that the induced map N ⟶ H is also finite. This in turn implies that the induced map N/[−1] ⟶ H is finite too (by definition of the geometric quotient).

Let us now consider the commutative diagram

[figure: N; E^{m}; E^{m−1}; H; (ℙ_{k}^{1})^{m} ,; (ℙ_{k}^{1})^{m−1}]

where the vertical maps are induced by the covering φ and the morphisms E^{m} ⟶ E^{m−1} and (ℙ_{k}^{1})^{m} ⟶ (ℙ_{k}^{1})^{m−1} are the projections to the first m − 1 coordinates. Then the induced morphism N ⟶ E^{m−1} is an isomorphism, and the morphism E^{m−1} ⟶ (ℙ_{k}^{1})^{m−1} is a generically separable flat covering of degree 2^{m−1}.

Below we show that the map N ⟶ H generically has degree 2, and the map H ⟶ (ℙ_{k}^{1})^{m−1} generically has degree 2^{m−2}. This statement implies statements a) and b) in the lemma. Indeed, first as N ⟶ H generically has degree 2, the induced map N/[−1] ⟶ H generically has degree 1, that is, it is birational. Second, the fact that the map H ⟶ (ℙ_{k}^{1})^{m−1} is quasi-finite and generically of degree 2^{m−2} implies that the last component of the multidegree of H is 2^{m−2}. “By symmetry” (or by a repetition of the argument with projections to different components) then all components of the multidegree are 2^{m−2}.

Note first that we have already established that both maps are generically separable, and that the product of the two degrees is 2^{m−1}. Therefore, it suffices to show that the extension of function fields k(N)|k(H) has separability degree 2.

We are going to apply the isomorphism E^{m−1} ⟶ N which is the inverse of the projection N ⟶ E^{m−1} and consider the extension k(E^{m−1})|k(H).

Let Ω := \overline{k(E^{m−1})}, let p_{i} : E^{m−1} ⟶ E be the projection to the i^{th} coordinate, and let P_{i} ∈ E(Ω) be the induced points. (That is, P_{i} is the morphism Spec(Ω) ⟶ Spec(k(E^{m−1})) ⟶ E^{m−1} ⟶^{p_{i}} E, where the first two morphisms are the canonical ones.) Let p_{m} := − ∑_{i=1}^{m−1} p_{i} and P_{m} := − ∑_{i=1}^{m−1} P_{i}.

Then the inverse of the projection N ⟶ E^{m−1} to the first m − 1 coordinates is given by (p_{1}, …, p_{m}); the corresponding Ω-valued point of N is given by (P_{1}, …, P_{m}).

The points P_{1}, …, P_{m−1} are linearly independent, since the maps p_{1}, …, p_{m−1} are linearly independent, the map Mor_{k}(E^{m−1}, E) ⟶ E(k(E^{m−1})) is injective (in fact, it is an isomorphism), and the map E(k(E^{m−1})) ⟶ Spec(Ω) is injective too.

Now let us consider the preimage of φ(P_{1}, …, P_{m}) = (φ ∘ P_{1}, …, φ ∘ P_{m}) ∈ H(Ω) in N(Ω). This set consists of all tuples (ϵ_{1}P_{1}, …, ϵ_{m}P_{m}) ∈ E^{m}(Ω) with ϵ_{i} = ±1 and ∑_{i=1}^{m} ϵ_{i}P_{i} = O. Clearly, there are exactly two such tuples: ±(P_{1}, …, P_{m}).

We conclude: There are exactly two Ω-valued points of E^{m−1} which induce the Ω-valued point (φ ∘ P_{1}, …, φ ∘ P_{m}) ∈ H(Ω) under the projection N ⟶ H. This means that there are exactly two extensions of the canonical inclusion k(E^{m−1}) ⟶ Ω to k(N). Therefore, the separability degree of the extension k(E^{m−1})|k(H) is 2.

We come to c). We still (wlog.) only consider the projection p : H ⟶ (ℙ_{k}^{1})^{m−1} to the first m − 1 components. As the map is quasi-finite and as H has multidegree (2^{m−2}, …, 2^{m−2}), each fiber has degree 2^{m−2}. With other words: The Hilbert polynomials of the fibers are equal to 2^{m−2}. With [Har77, Theorem 9.9] we conclude that p is flat.

Note that H is a projective over (ℙ^{1})_{k}^{m−1}, thus in particular proper. Moreover, p is quasi-finite. These two properties together are equivalent to being finite by [Gro61, Proposition 4.4.2]. □

Now clearly, if S is any irreducible polynomial in k[X_{1}, Y_{1}, …, X_{m}, Y_{m}] which is multihomogeneous, then S satisfies the conditions of Proposition 2.1 if and only if H = V (S). This establishes Proposition 2.1.

Thus the m^{th} summation polynomial (cf. Definition 2.2) with respect to φ is the (up to a multiplicative constant unique) polynomial S with V (S) = H.

Remark 3.3 Let α ∈ Aut(ℙ_{k}^{1}). Then H_{α∘φ,m} = α(H_{φ,m}), with other words: H_{α^{−1}∘φ,m} = α^{−1}(H_{φ,m}). This implies that S_{α^{−1}∘φ,m} = α^{∗}(S_{φ,m}).

We now discuss how the summation polynomials for elliptic curves in Weierstraß form can be given in an explicit and constructive way, following [Sem04].

Lemma 3.4 Let E be an elliptic curve in ℙ_{k}^{2} in Weierstraß form:

E = V (Y^{2}Z + a_{1}XY Z + a_{3}Y Z^{2} − (X^{3} + a_{2}X^{2}Z + a_{4}XZ^{2} + a_{6}Z^{3}))

with a_{1}, a_{2}, a_{3}, a_{4}, a_{6} ∈ k and O = [0 : 1 : 0]. Then the 3^{rd} summation polynomial of E with respect to x_{|E} is

((x_{1}^{2}x_{2}^{2} + x_{2}^{2}x_{3}^{2} + x_{1}^{2}x_{3}^{2}) − 2(x_{1}^{2}x_{2}x_{3} + x_{1}x_{2}^{2}x_{3} + x_{1}x_{2}x_{3}^{2})
−(a_{1}^{2} + 4a_{2})x_{1}x_{2}x_{3} − (a_{1}a_{3} + 2a_{4}) · (x_{1}x_{2} + x_{2}x_{3} + x_{1}x_{3})
−(a_{3}^{2} + 4a_{6}) · (x_{1} + x_{2} + x_{3})
−a_{1}^{2}a_{6} + a_{1}a_{3}a_{4} − a_{2}a_{3}^{2} − 4a_{2}a_{6} + a_{4}^{2}) · Y_{1}^{2}Y_{2}^{2}Y_{3}^{2} .

Sketch of a proof. Let S be the polynomial in the lemma. Using the inversion and addition formulae for elliptic curves in Weierstraß form (cf. [Sil86]), one can check (with a rather lengthy computation) that for all P_{1}, P_{2} ∈ E(\overline{k}), S(x(P_{1}), x(P_{2}), x(P_{1} + P_{2})) = 0. This implies that S_{3} divides S. As both polynomials have multidegree (2, 2, 2), it follows that they are equal. Let us note here that one only has to check that S(x(P_{1}), x(P_{2}), x(P_{1} + P_{3})) = 0 for P_{1} ≠ ±P_{2} and P_{1}, P_{2} ≠ O because then S vanishes on an open part of H_{3} and thus also on all of H_{3}. □

Let us indicate how the polynomial S was found, following [Sem04]: Let P_{1}, P_{2} ∈ E(\overline{k}) with P_{1}, P_{2} ≠ O and P_{1} ≠ ±P_{2}. Then clearly both

x(P_{1} +P_{2}) and x(P_{1} −P_{2}) satisfy the polynomial (x−x(P_{1} +P_{2}))(x−x(P_{1} − P_{2})). So we computed this polynomial over the field ℚ(a_{1}, a_{2}, a_{3}, a_{4}, a_{6}) and for “generic” P_{1}, P_{2}, using the computer algebra system MAGMA. The polynomial S is then obtained by multiplication with the denominator and homogenization.

Lemma 3.5 Let E still be an elliptic curve and φ : E ⟶ ℙ_{k}^{1} a covering of degree 2 with φ ∘ [−1] = φ. Let s, t ∈ ℕ with s, t ≥ 2. Then

S_{φ,s+t}(X_{1}, Y_{1}, …, X_{s+t}, Y_{s+t}) =
Res_{(X,Y)}(S_{φ,s+1}(X_{1}, Y_{1}, …, X_{s}, Y_{s}, X, Y),
S_{φ,t+1}(X_{s+1}, Y_{s+1}, …, X_{s+t}, Y_{s+t}, X, Y)) .

Here by Res_{(X,Y)} we mean the usual Sylvester resultant for homogeneous polynomials in X and Y of degrees 2^{s−1} and 2^{t−1}.

Proof. For (P_{1}, …, P_{s+t}) ∈ (E(\overline{k}))^{s+t} we have P_{1} + ⋯ + P_{s+t} = O if and only if there exists some P ∈ E(\overline{k}) with P_{1} + ⋯ + P_{s} + P = O and P_{s+1} + ⋯ + P_{s+t} − P = O.

It follows that topologically the hypersurface H_{s+t} is the image of V (S_{φ,s+1}(X_{1}, Y_{1}, …, X_{s}, Y_{s}, X, Y), S_{φ,t+1}(X_{s+1}, Y_{s+1}, …, X_{s+t−1}, Y_{s+t}, X, Y)) in (ℙ_{k}^{1})^{n}×Proj(k[X, Y]) under the projection to (ℙ_{k}^{1})^{n}. As H_{s+t} is irreducible it follows that the resultant in the lemma is (up to a multiplicative constant) a power of S_{φ,s+t}.

In order to prove that the resultant is (up to a constant) equal to S_{φ,s+t}, we consider their multidegrees.

The generic Sylvester resultant for polynomials of degrees a and b has degree b in the coefficients of the first polynomial and degree a in the coefficients of the second polynomial. We apply this with a = 2^{s−1} and b = 2^{t−1}. In our case we obtain a polynomial of degree 2^{s−1} · 2^{t−1} = 2^{s+t−2} in (X_{i}, Y_{i}) for all i = 1, …, s + t.

As S_{φ,s+t} has multidegree (2^{s+t−2}, …, 2^{s+t−2}), the result follows. □

The two preceding lemmata give rise to algorithmic constructions of the summation polynomials over finite fields.

First, given an elliptic curve in Weierstraß form and a covering of degree 2 φ : E ⟶ ℙ_{𝔽_{q}}^{1} with φ ∘ [−1] = φ (which means that the automorphism α ∈ Aut(ℙ_{k}^{1}) with φ = α ∘ x_{|E} is given), one can easily determine S_{φ,3} via Lemma 3.4 and Remark 3.3.

Further, one can compute S_{φ,m} for m ≥ 3 from S_{φ,m−1} and S_{φ,3} by applying the above lemma with s = m − 2 and t = 2. This computation can be performed via interpolation provided that q ≥ 2^{m−2} (which means that #ℙ^{1}(𝔽_{q}) ≥ 2^{m−2} + 1). For completeness we give here the interpolation result we apply.

Proposition 3.6 (Multihomogeneous interpolation)

a) Let \underline{d} ∈ ℕ^{n}, and let S := \{1, …, d_{1} + 1\} × ⋯ × \{1, …, d_{n} + 1}. Let k be a field, let (a_{i,j}, b_{i,j}) ∈ k^{2} − {0} for i = 1, …, n and j = 1, …, d_{i} + 1 such that for each i, the elements (a_{i,1} : b_{i,1}), …, (a_{i,d_{i}+1} : b_{i,d_{i}+1}) ∈ ℙ^{1}(k) are pairwise distinct, and let c\underline{j} ∈ k for \underline{j} ∈ S.

Then there is exactly one multihomogeneous polynomial F ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}] of multidegree \underline{d} with F (a_{1,j_{1}}, b_{1,j_{2}}, …, a_{n,j_{n}}, b_{n,j_{n}}) = c\underline{j} for all \underline{j} ∈ S.

b) Given a prime power q and elements as above over k = 𝔽_{q}, the interpolating polynomial F can be computed in a time of Poly((d_{1} + 1) ⋯ (d_{n} + 1) · log(q)).

Proof. Let us first consider the classical 1-dimensional interpolation problem in the context of homogeneous polynomials: Let d ∈ ℕ and (a_{j}, b_{j}) ∈ k^{2}−{0} for j = 1, …, d + 1 such that the induced elements in ℙ^{1}(k) are pairwise distinct. Moreover, let c_{1}, …, c_{d+1} ∈ k. Then there is exactly one homogeneous polynomial F (X, Y) ∈ k[X, Y] of degree d with F (a_{j}, b_{j}) = c_{j} for all j = 1, …, d+1. Moreover, with L_{j} := ∏_{ℓ≠j} \frac{b_{ℓ}X−a_{ℓ}Y}{a_{j}b_{ℓ}−a_{ℓ}b_{j}} we have F = ∑_{j} c_{j}L_{j}.

For the general case we proceed by induction on n.

Let us first prove the uniqueness. For this, let \underline{d}, S, k, and (a_{i,j}, b_{,j}) ∈ k^{2} − {0} for i = 1, …, n and j = 1, …, d_{i} + 1 be as in the proposition, and let F ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}] be of multidegree \underline{d} with F (a_{1,j_{1}}, b_{1,j_{2}}, …, a_{n,j_{n}}, b_{n,j_{n}}) = 0 for all \underline{j} ∈ S.

Then be induction hypothesis, for each j = 1, …, d_{n} + 1, F (X_{1}, Y_{1}, …, X_{n−1}, Y_{n−1}, a_{n,j}, b_{n,j}) = 0 ∈ k[X_{1}, Y_{1}, …, X_{n−1}, Y_{n−1}]. We now regard F (X_{1}, Y_{1}, …, X_{n}, Y_{n}) as a bivariate homogeneous polynomial in the ring k(X_{1}, Y_{1}, …, X_{n−1}, Y_{n−1})[X_{n}, Y_{n}]. Then by the uniqueness of the solution of the 1-dimensional interpolation problem, we conclude that F = 0.

We come to the existence. So let objects as in the proposition be given. For each j = 1, …, d_{n} + 1 there is by induction assumption exactly one

multihomogeneous polynomial C_{j} ∈ k[X_{1}, Y_{1}, …, X_{n−1}, Y_{n−1}] of multidegree (d_{1}, …, d_{n−1}) with C_{j}(a_{1,j_{1}}, b_{1,j_{2}}, …, a_{n−1,j_{n−1}}, b_{n−1,j_{n−1}}) = c\underline{j} for all \underline{j} ∈ S with j_{n} = j. Let L_{j} := ∏_{ℓ≠j} \frac{b_{ℓ}X_{n}−a_{ℓ}Y_{n}}{a_{j}b_{ℓ}−a_{ℓ}b_{j}} for j = 1, …, d_{n} + 1. Then the polynomial F := ∑_{j} C_{j}L_{j} fulfills the requirements.

The computational result can easily be obtained via a linear algebra algorithm. □

This gives:

Proposition 3.7 Given a natural number m ≥ 3, a prime power q with q ≥ 2^{m−2}, an elliptic curve E over 𝔽_{q} in Weierstraß form and a covering φ : E ⟶ ℙ_{𝔽_{q}}^{1} of degree 2 with φ ∘ [−1] = φ, one can compute the m^{th} summation polynomial of E with respect to φ in a time of Poly(e^{m^{2}} ·log(q)).

By passing to field extensions if necessary, one obtains Proposition 2.3.

4 Geometric background on the algorithm and analysis

The main purpose of this section is to prove Proposition 2.9. Additionally, we give some background information on the definition of the factor base from a geometric point of view.

4.1 Weil restrictions

We make use of Weil restrictions of schemes. Here we briefly recall the definition and some basic properties of Weil restrictions. For further information we refer to [BLR80, 7.6] and [Die01, Chapter 1].

Let S′ and S be locally noetherian schemes, and let a flat covering S′ ⟶ S (a finite and flat morphism) be fixed. (Note here that a flat covering is locally free (see [Mat89, Theorem 7.10]).) Let X′ be an S′-scheme such that the fibers of X′ over S′ are quasi-projective. Then one can show that the functor from S-schemes to sets Z ↦ Mor_{S′}(Z_{S′}, X′) is representable by an S-scheme; the (up to unique isomorphism unique) representing object is called the Weil restriction of X′ with respect to S′ ⟶ S. We denote it by Res_{S}^{S′}(X′).^{4}

A reformulation of this definition is: The Weil restriction of X′ with respect to S′ ⟶ S is a an S-scheme Res_{S}^{S′}(X′) together with an S′-morphism u : (Res_{S}^{S′}(X′))_{S′} ⟶ X′ such that the following holds: Whenever Z is an S-scheme, and α : Z ×_{S} S′ = Z_{S′} ⟶ X′ is an S′-morphism, there is a unique S-morphism β : Z ⟶ Res_{S}^{S′}(X′) with α = u ∘ β_{S′}, where β_{S′} := β ×_{S} S′ = β ×_{S} id_{S′}. We denote the morphism β by α_{⊚}.

The assignment X ↦ Res_{S}^{S′}(X′) gives rise to a functor (which we call scalar restriction functor) from the category of S′-schemes with quasi-pro-jective fibers to the category of S-schemes. Moreover, if X′ is an affine S′-scheme, then Res_{S}^{S′}(X′) is an affine S-scheme.

We will use the following two lemmata. The proofs are rather easy and therefore omitted.

Lemma 4.1 Let S′ ⟶ S be as above, and let X′, Y′, W′ be S′-schemes with S′-morphisms X′ ⟶ W′ and Y′ ⟶ W′. Then we have a Cartesian diagram

\xymatrix{Res_{S}^{S′}(X′ ×_{W′} Y′) \ar[r] \ar[d] & Res_{S}^{S′}(Y′) \ar[d] \\ Res_{S}^{S′}(X′) \ar[r] & Res_{S}^{S′}(W′)}

with the obvious canonical morphisms.

Lemma 4.2 Let S′ ⟶ S as above, let T be an S-scheme, and let T′ := T ×_{S} S′. Let X′ be a T′-scheme with structural morphism α : X′ ⟶ T′.

Let v : (Res_{T}^{T′}(X′))_{T′} ⟶ X′ be the universal morphism; v is thus a T′-morphism. We have (Res_{T}^{T′}(X′)) ×_{T} T′ ≃ (Res_{T}^{T′}(X′)) ×_{S} S′, and v is in particular an S′-morphism. Thus by the universal property of Res_{S}^{S′}(X′) we have an induced S-morphism v_{⊚} : Res_{T}^{T′}(X′) ⟶ Res_{S}^{S′}(X′).

4The similarity between the notations for Weil restrictions and resultants is accidental.

Now we have a Cartesian diagram

\xymatrix{Res_{T}^{T′}(X′) \ar[d] \ar[r] & Res_{S}^{S′}(X′) \ar[d] \\ T \ar[r] & Res_{S}^{S′}(T′) ,}

where the morphisms are defined as follows: The left morphism is the structural morphism, the right morphism is Res_{S}^{S′}(α), the upper morphism is v_{⊚}, and the lower morphism is the morphism id_{⊚} : T ⟶ Res_{S}^{S′}(T′) corresponding to the identity on T′ under the defining functorial property of Res_{S}^{S′}(T′).

Let now K|k be a finite separable field extension. Then if X′ is a quasiprojective (resp. projective) scheme over K, Res_{k}^{K}(X′) is a quasi-projective (resp. projective) scheme of dimension [K : k]·dim(X′) over k. Note that by the defining functorial property of the Weil restriction we have in particular a bijection

X′(K) = Mor_{K}(Spec(K), X′) ⟶ Res_{k}^{K}(X′)(k) = Mor_{k}(Spec(k), Res_{k}^{K}(X′)),

P ↦ P_{⊚} .

If X′ is a group scheme over K, Res_{k}^{K}(X′) is in a natural way again a group scheme, and if A′ is an abelian variety over K, then Res_{k}^{K}(A′) is in a natural way an abelian variety too.

Let K|k now be an extension of finite fields of degree n, and let σ_{K|k} be the relative Frobenius automorphism of K|k. We denote the induced isomorphism Spec(k) ⟶ Spec(k) again by σ_{K|k}. Let X′ be a quasi-projective K-scheme. Then we have a canonical isomorphism

(Res_{k}^{K}(X′))_{K} ≃ ∏_{i=0}^{n−1} σ_{K|k}^{i}(X′)

of K-schemes under which the universal morphism u : (Res_{k}^{K}(X′))_{K} ⟶ X′ corresponds to the projection

u : ∏_{i=0}^{n−1} σ_{K|k}^{i}(X′) ⟶ X′ .

Moreover, if Z is any k-scheme and α : Z_{K} ⟶ X′ is a morphism, then (α_{⊚})_{K} corresponds to

(α, σ_{K|k}(α), …, σ_{K|k}^{n−1}(α)) : Z_{K} ⟶ ∏_{i=0}^{n−1} σ_{K|k}^{i}(X′)

and if φ : X′ ⟶ Y′ is a morphism of quasi-projective K-schemes, then Res_{k}^{K}(φ) corresponds to

φ × σ_{K|k}(φ) × ⋯ × σ_{K|k}^{n−1}(φ) : ∏_{i=0}^{n−1} σ_{K|k}^{i}(X′) ⟶ ∏_{i=0}^{n−1} σ_{K|k}^{i}(Y′) .

4.2 Intersection theory in (ℙ_{k}^{1})^{n}

The proof of Proposition 2.9 relies crucially on intersection theory in products of projective lines and on the theory of resultants for multihomogeneous polynomials. In this subsection we state some results on intersection theory and resultants in this specific situation.

Let for this subsection k be any field.

Notation 4.3 Let V be a fixed quasi-projective variety, and let X be a closed subscheme of V. Then we denote the class of X in the Chow ring of V by [X]. (We do not fix a notation for the cycle corresponding to a closed subscheme as we never perform operations with cycles but only with classes.)

We have the following explicit description of the Chow ring of (ℙ_{k}^{1})^{n}:

Proposition 4.4 Let h_{i} := [V (X_{i})] ∈ CH((ℙ_{k}^{1})^{n}) for i = 1, …, n. Then we have an isomorphism ℤ[H_{1}, …, H_{n}]/(H_{1}^{2}, …, H_{n}^{2}) ⟶ CH((ℙ_{k}^{1})^{n}) , [H_{i}] ↦ h_{i}.

This proposition can easily be derived from a general result on the Chow rings of toric varieties (cf. the proposition on page 106 of [Ful93, Section 5.2]). We remark here that the book [Ful93] is concerned with toric varieties over the complex numbers. However, analytic arguments play a minor role in the exposition, and the few such arguments can rather easily be replaced with algebraic arguments. In particular, the proposition just mentioned holds over arbitrary fields.

Example 4.5 The class of an effective Cartier divisor on (ℙ_{k}^{1})^{n} of multidegree (d_{1}, …, d_{n}) is d_{1}h_{1} + ⋯ + d_{n}h_{n}.

Let us consider the pull-back and push-forward homomorphisms associated with the canonical projections between products of ℙ_{k}^{1}’s. The following considerations follow immediately from the axioms of intersection theory in [Har77, Appendix A].

For n_{1} > n_{2}, let p : (ℙ_{k}^{1})^{n_{1}} ⟶ (ℙ_{k}^{1})^{n_{2}} be the projection to the first n_{2} components. Let us denote by h_{i} for i = 1, …, n_{1} or i = 1, …, n_{2} the class of V (X_{i}) in any of the two Chow rings.

Then the pull-back p^{∗} : CH((ℙ_{k}^{1})^{n_{2}}) ⟶ CH((ℙ_{k}^{1})^{n_{1}}), which is a ring homomorphism, is given by the homomorphism which corresponds to the obvious inclusion under the isomorphism in Proposition 4.4. This means that it is given by p^{∗}(h_{i}) = h_{i}.

The push-forward p_{∗} : CH((ℙ_{k}^{1})^{n_{1}}) ⟶ CH((ℙ_{k}^{1})^{n_{2}}), which is a group homomorphism, is given as follows:

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

For completeness we mention the following lemma.

Lemma 4.7 Let F_{1}, …, F_{n} be multihomogeneous polynomials. Let the multidegree of F_{i} be (d_{i,1}, …, d_{i,n}), and let D := (d_{i,j})_{i,j}.

a) The 0-cycle [V (F_{1})] ⋯ [V (F_{n})] has degree Perm(D), the permanent of D. In particular, if the multidegree of each F_{i} is (d, …, d) for a common d ∈ ℕ, then the cycle has degree n! · d^{n}.

b) The degree 0 part of the class of V (F_{1}, …, F_{n}) in the Chow ring has degree ≤ Perm(D).

c) We have equality in b) if and only if V (F_{1}, …, F_{n}) is zero-dimensional.

Sketch of a proof. Part a) follows immediately from Proposition 4.4.

Part b) can easily be obtained from Krull’s Hautidealsatz and Axiom A7 on intersection theory in [Har77, Appendix A].

For part c) see [Ful84, Proposition 8.2]. □

Intersection theory and the theory of resultants are closely connected. Let us recall the definition and basic properties in the situation under consideration.

Note for the following that according to our convention ℕ = {1, 2, …}. Let us fix some n ∈ ℕ. Let for \underline{d} ∈ ℕ M\underline{d} be the set of monomials of multidegree \underline{d} in k[X_{1}, Y_{1}, …, X_{n}, Y_{n}].

Let for each i = 1, …, n + 1 some \underline{d}^{(i)} ∈ ℕ^{n} be given. We want to define the generic resultant for multihomogeneous polynomials of multidegrees \underline{d}^{(1)}, …, \underline{d}^{(n+1)} over k. For this we consider a “universal coefficient ring”, which is a multivariate polynomial ring over k which for each pair (i, m) with m ∈ M_{\underline{d}_{(i)}} has one indeterminate c_{i,m}, that is, it is the ring k[(c_{i,m})_{i=1,...,n+1,m∈M_{\underline{d}_{(i)}}} ]. We define the generic system of n + 1 multiho-

mogeneous polynomials with multidegrees \underline{d}^{(1)}, …, \underline{d}^{(n+1)} as G_{1}, …, G_{n+1} ∈ k[(c_{i,m})_{i,m}][X_{1}, Y_{1}, …, X_{n}, Y_{n}] with G_{i} = ∑_{m∈M_{\underline{d}_{(i)}}} c_{i,m} m.

The generic resultant for multihomogeneous systems with the given degrees is then an element of k[(c_{i,m})_{i,m}], and the resultant of a particular system of multihomogeneous polynomials with the given degrees is obtained by substituting the coefficients of the polynomials for the generic coefficients. The key statements are summarized in the following proposition.

Proposition 4.8

a) There is an irreducible polynomial Res ∈ k[(c_{i,m})_{i=1,...,n+1,m∈M_{\underline{d}_{(i)}}} ] which for i = 1, …, n + 1 is homogeneous in the coefficients of the i^{th} generic polynomial and which has the following property: For all field extensions K|k and all systems of multihomogeneous polynomials F_{1}, …, F_{n+1} ∈ K[X_{1}, Y_{1}, …, X_{n}, Y_{n}], where F_{i} has multidegree \underline{d}^{(i)}, we have Res(F_{1}, …, F_{n+1}) = 0 if and only if V (F_{1}, …, F_{n+1}) is non-empty. Here Res(F_{1}, …, F_{n+1}) is obtained by substituting the coefficients of the polynomials for the generic coefficients.

b) The polynomial Res with the above properties is unique up to multiplication by a non-trivial constant.

c) The polynomial Res is geometrically irreducible.

d) For each i = 1, …, n + 1, Res has degree Perm(D_{i}) in the coefficients of the i^{th} generic polynomial, where D_{i} is obtained from the matrix

( \underline{d}^{(1)} ; ⋮ ; \underline{d}^{(n+1)} ) by deleting the i^{th} row.

This proposition follows from general results [GKZ94, subsection 3.3 A] applied to multihomogeneous polynomials. Note that all results in [GKZ94] are formulated over the complex numbers, but the proof of this result holds over arbitrary fields as well.

4.3 Background on the factor base

As at the end of subsection 4.1, let K|k be an extension of finite fields of degree n. Let E be an elliptic curve over K, and let us fix a covering φ : E ⟶ ℙ_{K}^{1} of degree 2 with φ ∘ [−1] = φ.

Let ι = id_{⊚} : ℙ_{k}^{1} ⟶ Res_{k}^{K}(ℙ_{K}^{1}) be the morphism corresponding to the identity on ℙ_{K}^{1}. One can easily see (for example via base change to K) that ι is a closed immersion.

Let V be the preimage of ι(ℙ_{k}^{1}) under Res_{k}^{K}(φ) : Res_{k}^{K}(E) ⟶ Res_{k}^{K}(ℙ_{K}^{1}).

This means by definition that we have a Cartesian 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}) .}  (3)

Note that Res_{k}^{K}(φ) : Res_{k}^{K}(E) ⟶ Res_{k}^{K}(ℙ_{K}^{1}) is a flat covering of degree 2^{n} (as one sees after base change to K), and therefore V ⟶ ℙ_{k}^{1} is a flat covering of degree 2^{n} too.

Let us now explain the connection of these definitions to the definition of the factor base in the algorithm: Let us consider a particular run of the algorithm. Then under the bijection ℙ^{1}(K) ≃ Res_{k}^{K}(ℙ_{K}^{1})(k) the inclusion ℙ^{1}(k) ⊆ ℙ^{1}(K) corresponds to ι(ℙ_{k}^{1}(k)) ⊆ Res_{k}^{K}(ℙ_{K}^{1}))(k). Therefore the factor base F = (φ^{−1}(ℙ_{k}^{1})(k)) ⊆ E(K) corresponds to V (k) under the bijection E(K) ≃ Res_{k}^{K}(E)(k). One can therefore say that the factor base is defined in a “geometric way” – something that is not immediately apparent from the definition of the factor base in the algorithm.

The addition on the Weil restriction induces a morphism V^{n} ⟶ Res_{k}^{K}(E), and – again under the bijection E(K) ≃ Res_{k}^{K}(E)(k) – for P ∈ E(K) the tuples (P_{1}, …, P_{n}) ∈ E(K)^{n} with φ(P_{i}) ∈ ℙ^{1}(k) and ∑_{i} P_{i} = P correspond to the k-valued points of the fiber of V^{n} ⟶ Res_{k}^{K}(E) at P_{⊚}, the k-rational point of Res_{k}^{K}(E) corresponding to P.

We now study V under Condition 2.7.

Proposition 4.9 Let Condition 2.7 be satisfied. Then V is geometrically reduced and geometrically irreducible (and thus birational to a curve).

Proof. By (3) and Lemma 4.2 we have V ≃ Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(E), with respect to the covering φ : E ⟶ ℙ_{k}^{1}. This implies that

V_{K} ≃ E ×_{ℙ_{K}^{1}} σ_{K|k}(E) ×_{ℙ_{K}^{1}} ⋯ ×_{ℙ_{K}^{1}} σ_{K|k}^{n−1}(E) ,  (4)

where the morphisms are φ : E ⟶ ℙ_{K}^{1}, …, σ_{K|k}^{n−1}(φ) : σ_{K|k}^{n−1}(E) ⟶ ℙ_{K}^{1}.

Let us now fix an algebraic closure \overline{k(x)} of k(x), and let again σ be the relative Frobenius automorphism of \overline{k}|k. Let us then prolong σ first to \overline{k}(x) via σ(x) := x, and let us fix any automorphism of \overline{k(x)}|k(x) which restricts to σ; let us denote this automorphism again by σ. Moreover, let us fix an injection of \overline{k}(E) into \overline{k(x)} over k(x).

We now consider the total quotient ring of the scheme V\overline{k}, which is isomorphic to

\overline{k}(E) ⊗_{\overline{k}(x)} σ(\overline{k}(E)) ⊗_{\overline{k}(x)} ⋯ ⊗_{\overline{k}(x)} σ^{n−1}(\overline{k}(E)) .

By Condition 2.7 for i = 1, …, n − 1, the extension σ^{i}(\overline{k}(E))|\overline{k}(x) is ramified at σ^{i}(R), but for any j = 0, …, i − 1, the extension σ^{j}(\overline{k}(E))|\overline{k}(x) is unramified at σ^{i}(R), thus the extension \overline{k}(E)σ(\overline{k}(E)) ⋯ σ^{i−1}(\overline{k}(E))|\overline{k}(x) in \overline{k(x)} is also unramified at σ^{i}(R). Thus σ^{i}(\overline{k}(E)) is not contained in \overline{k}(E)σ(\overline{k}(E)) ⋯ σ^{i−1}(\overline{k}(E)). It follows therefore by induction that the extension \overline{k}(E)σ(\overline{k}(E)) ⋯ σ^{n−1}(\overline{k}(E))|\overline{k}(x) in \overline{k(x)} has degree 2^{n}. Thus the total quotient ring of V\overline{k} is isomorphic to the composite \overline{k}(E)σ(\overline{k}(E)) ⋯ σ^{n−1}(\overline{k}(E)) in \overline{k(x)} and therefore a field. We see that V\overline{k} is reduced and irreducible, thus V is geometrically reduced and geometrically irreducible. □

Proposition 4.10 Let us still assume that Condition 2.7 is satisfied, let C be the curve which is birational to V, and let π : C ⟶ V be a birational morphism. Then

a) The genus of C is ≤ (2n − 1) · (2^{n} − 1).

b) C(\overline{k}) contains at most n · 2^{n+2} points which map to singular points under the birational morphism π : C ⟶ V.

Proof. By a general result on elementary abelian extensions (see e.g. [KR89]) we have

g(C) = ∑_{L} g(L) ,

where L runs over all subextensions of \overline{k}(C)|\overline{k}(x) of degree 2. We show below that the genus of a function field L as in the sum is always ≤ 2n − 1. This implies that g(C) ≤ (2n − 1) · (2^{n} − 1).

To show the claim on the subfields L we proceed with a case distinction. \underline{Let q be even.} By Artin-Schreier theory every subfield L of \overline{k(x)}|\overline{k}(x) of degree 2 corresponds to a 1-dimensional subspace of the 𝔽_{2}-vector space \overline{k}(x)/P(\overline{k}(x)), where P is the Artin-Schreier operator.

If now \overline{k}(E) corresponds to ⟨\overline{f}⟩, where \overline{f} is the residue class of some f ∈ \overline{k}(x), then each field L as in the sum corresponds to ⟨a_{0}\overline{f} + a_{1}\overline{σ(f)} + ⋯ + a_{n−1}\overline{σ^{n−1}(f)}⟩ for a uniquely defined tuple (a_{0}, …, a_{n−1}) ∈ 𝔽_{2}^{n} − \{0\}. \underline{Let first j(E) = 0.} In this case the extension \overline{k}(E)|\overline{k}(x) is ramified at one place, and \overline{k}(E) corresponds to some space ⟨\overline{f}⟩, where f is either a polynomial of degree 3 or of the form \frac{g}{(x−λ)^{3}} for λ ∈ \overline{k} and deg(g) = 3.

Using [Sti93, Proposition III.7.8] one sees: If L is any field as in the sum, then L|\overline{k}(x) is ramified at at most n places (this is also immediately obvious), and the corresponding discriminant exponents are all 4. This implies that the genus of L is ≤ 2n − 1. \underline{Let now j(E) ≠ 0.} In this case \overline{k}(E)|\overline{k}(x) is ramified at 2 places, and \overline{k}(E) corresponds to ⟨\overline{f}⟩, where f is the sum of two distinct polynomials f_{1}, f_{2} such that each of these polynomials is either x or \frac{1}{x−a} for some a ∈ \overline{k}. Now each subfield L as in the sum is ramified over at most 2n places and the different exponents are all 2. Again the genus of L is ≤ 2n − 1.

\underline{Let q be odd.} In this case \overline{k}(E)|\overline{k}(x) is (tamely) ramified at 4 places. If thus L is as in the sum, L|\overline{k}(x) is ramified at at most 4n places. Thus the genus of L is ≤ 2n − 1.

We come to b). Let S be the set of points of ℙ^{1}(\overline{k}) over which one of the coverings σ^{i}(E) ⟶ ℙ1 ; \overline{k} is ramified. Using the fact that a morphism obtained from an étale morphism via base change is étale we obtain: The canonical morphism V ⟶ ℙ_{k}^{1} is étale outside S. This implies that V is smooth outside the preimage of S, and the birational morphism π : C ⟶ V is an isomorphism outside the preimage of S. With other words: All points in C(\overline{k}) which map to singular points of V are contained in the preimage of S.

As the covering C ⟶ ℙ_{k}^{1} has degree 2^{n}, the preimage of the set S has at most #S · 2^{n} ≤ 4n · 2^{n} elements. □

Proposition 4.11 Let k = 𝔽_{q}, and let n ≥ 2 and log_{2}(q) ≥ 7n. Then under Condition 2.7,

#\{P ∈ E(K) | φ(P) ∈ ℙ^{1}(k)\} = #V (k) ≥ \frac{1}{2} · (q + 1) .

Proof. By the above propositions and the Hasse-Weil bound we have

#V (k) ≥ q+1−2·(2n−1)·(2^{n}−1)·q^{\frac{1}{2}} −n·2^{n+2}+1 ≥ q+1−n·2^{n+2}·(q^{\frac{1}{2}} +1) .

Now, q^{\frac{1}{2}} + 1 ≤ 2 · \frac{q+1}{q^{\frac{1}{2}}} and thus

n·2^{n+2}·(q^{\frac{1}{2}} +1) ≤ 2^{\frac{n}{2}} ·\frac{2^{n+3}}{q^{\frac{1}{2}}} ·(q+1) = \frac{2^{\frac{3}{2} n+4}}{q^{\frac{1}{2}}} ·\frac{q + 1}{2} ≤ \frac{2^{\frac{7}{2} n}}{q^{\frac{1}{2}}} ·\frac{q + 1}{2} = (\frac{2^{7n}}{q} )^{\frac{1}{2}} ·\frac{q + 1}{2} .

By assumption this is ≤ \frac{q+1}{2} and thus #V (k) ≥ \frac{q+1}{2}. □

4.4 The role of the summation polynomials

Let the hypersurface H = H_{n+1} of (ℙ_{k}^{1})^{n+1} be defined as in Section 3. By applying the scalar restriction functor, we obtain:

Res_{k}^{K}(H) ⟶ Res_{k}^{K}((ℙ_{K}^{1})^{n+1}) ≃ (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1} .

Via base change to K one sees immediately that we have a closed immersion.

Let X be the scheme-theoretic preimage of Res_{k}^{K}(H) in (ℙ_{k}^{1})^{n}×Res_{k}^{K}(ℙ_{K}^{1}) under the closed immersion ι × ι × ⋯ × ι × id : (ℙ_{k}^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}) ⟶ Res_{k}^{K}((ℙ^{1}))^{n+1}. This means by definition that we have a Cartesian diagram

\xymatrix{X \ar@{^{(}->}[d] \ar@{^{(}->}[r] & Res_{k}^{K}(H) \ar@{^{(}->}[d] \\ (ℙ_{k}^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}) \ar@{^{(}->}[r] & (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1} .}  (5)

Note that – again under the obvious bijections – the elements of X(k) correspond to the tuples (Q_{1}, …, Q_{n}, Q) with Q_{i} ∈ ℙ^{1}(k) and Q ∈ ℙ^{1}(K) with (Q_{1}, …, Q_{n}, Q) ∈ H(K). The latter condition means of course that there are P_{1}, …, P_{n}, P ∈ E(\overline{K}) with φ(P_{i}) = Q_{i}, φ(P) = Q and ∑_{i} P_{i} = P.

Notation 4.12 Let p_{1} : (ℙ_{k}^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}) ⟶ (ℙ_{k}^{1})^{n} and p_{2} : (ℙ_{k}^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}) ⟶ Res_{k}^{K}(ℙ_{K}^{1}) be the two projections.

Lemma 4.13 (p_{1})_{|X} : X ⟶ (ℙ_{k}^{1})^{n} is a flat covering of degree 2^{(n−1)·n}.

Proof. By Proposition 3.2 c) the projection to the first n components H ⟶ (ℙ_{K}^{1})^{n} is a flat covering of degree 2^{n−1}. Therefore the induced map Res_{k}^{K}(H) ⟶ Res_{k}^{K}((ℙ_{K}^{1})^{n}) ≃ (Res_{k}^{K}(ℙ_{K}^{1}))^{n} is a flat covering of degree 2^{(n−1)·n}. The map (p_{1})_{|X} : X ⟶ (ℙ_{k}^{1})^{n} is obtained from this map via base change with ι × ⋯ × ι : (ℙ_{k}^{1})^{n} ⟶ (Res_{k}^{K}(ℙ_{K}^{1}))^{n}. □

Notation 4.14 Let G be the graph of −a_{n} : V^{n} ⟶ Res_{k}^{K}(E), where a_{n} is the restriction of the addition morphism to V^{n}. (Note the minus sign!)

As in Section 3 let for m ∈ ℕ N_{m} be the kernel of the addition morphism E^{m} ⟶ E. One easily sees that Res_{k}^{K}(N_{m}) is (as a subscheme of Res_{k}^{K}(E^{m})) the kernel of the addition homomorphism on Res_{k}^{K}(E^{m}). Let now N := N_{n+1}. By considering Z-valued points for any k-scheme Z, one obtains immediately:

Lemma 4.15 G is the scheme-theoretic intersection of V^{n} × Res_{k}^{K}(E) and Res_{k}^{K}(N) in Res_{k}^{K}(E^{n+1}) ≃ (Res_{k}^{K}(E))^{n+1}.

Proposition 4.16 There is a canonical surjective morphism G ⟶ X. Moreover, if Condition 2.7 is satisfied, then X is geometrically irreducible.

Proof. Let us consider the commutative diagram

[figure: G; Res_{k}^{K}(N); X; Res_{k}^{K}(H); V^{n} × Res_{k}^{K}(E); (Res_{k}^{K}(E))^{n+1}; (ℙ_{k}^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}); (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1}]

with the obvious canonical morphisms. As by definition of X the right-lower subdiagram (i.e. diagram (5)) is Cartesian, we have an induced morphism G ⟶ X.

It suffices to prove the surjectivity on \overline{k}-valued points. So let Q ∈ X(\overline{k}). As the map N ⟶ H is surjective, so is Res_{k}^{K}(N) ⟶ Res_{k}^{K}(H). Let us consider Q as a point in Res_{k}^{K}(H)(\overline{k}), and let us fix a preimage P ∈ Res_{k}^{K}(N)(\overline{k}).

We claim that P lies in G(\overline{k}), or with other words that the image of P in (Res_{k}^{K}(E))^{n+1}(\overline{k}) lies in (V^{n} × Res_{k}^{K}(E))(\overline{k}). For this we have to check that the image of P in Res_{k}^{K}(ℙ_{K}^{1}))(\overline{k}) lies in ((ℙ^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}))(\overline{k}). But this is obvious as the image is nothing but the point Q we started with.

Let now Condition 2.7 be satisfied. By Proposition 4.9 V is then geometrically reduced and geometrically irreducible, thus so is V^{n}, which is isomorphic to the graph G. As the map G ⟶ X is surjective, X is then also geometrically irreducible. □

Let us now fix some Q ∈ ℙ^{1}(K). Following our notation, let Q_{⊚} be the corresponding k-rational point of Res_{k}^{K}(ℙ_{K}^{1}). Let X_{Q_{⊚}} be the fiber of X at Q_{⊚}, that is, we have the Cartesian diagram

\xymatrix{X_{Q_{⊚}} \ar@{^{(}->}[r] \ar@{^{(}->}[d] & X \ar@{^{(}->}[d] \\ (ℙ_{k}^{1})^{n} \ar@{^{(}->}[r] \ar[d] & (ℙ_{k}^{1})^{n} × Res_{k}^{K}(ℙ_{K}^{1}) \ar[d] \\ Spec(k) \ar@{^{(}->}[r]^{Q_{⊚}} & Res_{k}^{K}(ℙ_{K}^{1}) .}

Then we have the following connection with the decomposition problem:

Proposition 4.17 As a subscheme of (ℙ_{k}^{1})^{n},  X_{Q_{⊚}}  is

V (S^{(1)}, …, S^{(n)}), where the polynomials S^{(j)} ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}] are defined as in Equation (2).

We show first:

Lemma 4.18 Let H_{Q} ⊂ (ℙ_{K}^{1})^{n} be the restriction of H to (ℙ_{K}^{1})^{n} via the closed immersion id × ⋯×id ×Q : (ℙ_{K}^{1})^{n} ≃ (ℙ_{K}^{1})^{n}×_{K}Spec(K) ⟶ (ℙ_{K}^{1})^{n+1}. Then we have a Cartesian diagram

\xymatrix{X_{Q_{⊚}} \ar@{^{(}->}[r] \ar@{^{(}->}[d] & Res_{k}^{K}(H_{Q}) \ar@{^{(}->}[d] \\ (ℙ_{k}^{1})^{n} \ar@{^{(}->}[r] & (Res_{k}^{K}(ℙ_{K}^{1}))^{n} ,}

where the lower arrow is given by ι × ⋯ × ι.

Proof. We have Res_{k}^{K}(Spec(K)) = Spec(k) and Res_{k}^{K}(Q) = Q_{⊚}. By Lemma 4.1 the defining Cartesian diagram

\xymatrix{H_{Q} \ar@{^{(}->}[r] \ar@{^{(}->}[d] & H \ar@{^{(}->}[d] \\ (ℙ_{K}^{1})^{n} \ar@{^{(}->}[r] & (ℙ^{1})^{n+1}}

gives rise to the Cartesian diagram

\xymatrix{Res_{k}^{K}(H_{Q}) \ar@{^{(}->}[r] \ar@{^{(}->}[d] & Res_{k}^{K}(H) \ar@{^{(}->}[d] \\ (Res_{k}^{K}(ℙ_{K}^{1}))^{n} \ar@{^{(}->}[r] & (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1} ,}

where the lower arrow is given by id × ⋯ × id ×Q_{⊚} : (Res_{k}^{K}(ℙ_{K}^{1}))^{n} ≃ (Res_{k}^{K}(ℙ_{K}^{1}))^{n} ×_{k} Spec(k) ⟶ (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1}.

Now X_{Q_{⊚}} is the pull-back of Res_{k}^{K}(H) to (ℙ_{k}^{1})^{n} under the map ι × ⋯ × ι × Q_{⊚} : (ℙ_{k}^{1})^{n} ≃ (ℙ_{k}^{1})^{n} ×_{k} Spec(k) ⟶ (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1}. This implies that we have a Cartesian diagram

\xymatrix{X_{Q_{⊚}} \ar@{^{(}->}[r] \ar@{^{(}->}[d] & Res_{k}^{K}(H_{Q}) \ar@{^{(}->}[r] \ar@{^{(}->}[d] & Res_{k}^{K}(H) \ar@{^{(}->}[d] \\ (ℙ^{1})_{k}^{n} \ar@{^{(}->}[r] & (Res_{k}^{K}(ℙ_{K}^{1}))^{n} \ar@{^{(}->}[r] & (Res_{k}^{K}(ℙ_{K}^{1}))^{n+1} .}

□

We come to the proof of Proposition 4.17.

By Lemma 4.18 and Lemma 4.2 we have a commutative diagram

\xymatrix{X_{Q_{⊚}} \ar@{^{(}->}[dr] \ar[rr]^{∼} &  & Res_{(ℙ_{k}^{1})^{n}}^{(ℙ_{K}^{1})^{n}}(H_{Q}) \ar@{-->}[dl] \\  & (ℙ_{k}^{1})^{n} ,}

where the arrow to the left is the structural morphism, which of course is then also a closed immersion.

To establish the result we thus have to show that as a closed subscheme of (ℙ_{k}^{1})^{n}, Res_{(ℙ_{k}^{1})^{n}}^{(ℙ_{K}^{1})^{n}}(H_{Q}) is equal to V (S^{(1)}, …, S^{(n)}).

Let now S_{φ,n+1} be the same summation polynomial as in subsection 2.1 (recall that the (n + 1)^{th} summation polynomial with respect to φ is only unique up to multiplication by a non-trivial constant). Also, let b_{1}, …, b_{n} be the fixed k-basis of K from subsection 2.1. Note that b_{1}, …, b_{n} is then also a basis of the free k[x_{1}, …, x_{n}]-module K[x_{1}, …, x_{n}]. Moreover, let S′ := S_{φ,n+1}(X_{1}, Y_{1}, …, X_{n}, Y_{n}, Q) be the polynomial obtained by inserting the same coordinates of Q = φ(P) into the summation polynomial as in 2.1 (again these are only unique up to multiplication by a non-trivial constant).

We now prove the result by restriction to affine parts of (ℙ_{k}^{1})^{n}.

Let for the moment X_{i,1} := X_{i} and X_{i,2} := Y_{i}. Moreover, let for some multihomogeneous polynomial F ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}] U_{F} := (ℙ_{k}^{1})^{n} − V (F) be the corresponding open subscheme.

One can now show that for any \underline{a} ∈ \{1, 2\}^{n}, the restrictions of both schemes to U_{X_{1,a_{1}}} ∩ U_{X_{2,a_{2}}} ∩ ⋯ ∩ U_{X_{n,an}} are equal; and this implies that the schemes are equal. For notational convenience we consider in the following the case of \underline{a} = (2, …, 2) (“dehomogenization with respect to Y_{1}, …, Y_{n}”); the other cases can be established in exactly the same way.

Let s(x_{1}, …, x_{n}) := S′(x_{1}, 1, x_{2}, 1, …, x_{n}, 1) ∈ K[x_{1}, …, x_{n}]. Then H_{Q} ∩ 𝔸_{k}^{n} ⊆ 𝔸_{k}^{n} = Spec(k[x_{1}, …, x_{n}]) corresponds to the quotient ring k[x_{1}, …, x_{n}]/(s) of k[x_{1}, …, x_{n}].

As the formation of the Weil restriction commutes with base-change on the base, we have (Res_{(ℙ_{k}^{1})^{n}}^{(ℙ_{K}^{1})^{n}}(H_{Q})) ∩ 𝔸_{k}^{n} = Res_{𝔸_{k}^{n}}^{𝔸_{K}^{n}}(H_{Q} ∩ 𝔸_{K}^{n}) as closed

subschemes of 𝔸_{k}^{n}. A defining system of polynomials for Res_{𝔸_{k}^{n}}^{𝔸_{K}^{n}}(H_{Q} ∩ 𝔸_{K}^{n}) can be derived via the well-known method to obtain defining equations for Weil restrictions of affine schemes over rings (see example [Die01, Chapter 1] or the proof of [BLR80, §7.6., Theorem 4]):

Let s^{(1)}, …, s^{(n)} ∈ k[x_{1}, …, x_{n}] be defined by the equation

∑_{j} b_{j} s^{(j)} = s .

Then Res_{𝔸_{k}^{n}}^{𝔸_{K}^{n}}(H_{Q} ∩ 𝔸_{K}^{n}) = Spec(k[x_{1}, …, x_{n}]/(s^{(1)}, …, s^{(n)})) = V (s^{(1)}, …, s^{(n)}) ⊂ 𝔸_{k}^{n}. But the s^{(j)} are exactly the dehomogenizations of the polynomials S^{(j)}, and thus (X_{Q_{⊚}}) ∩ 𝔸_{k}^{n} = (Res_{(ℙ_{k}^{1})^{n}}^{(ℙ_{K}^{1})^{n}}(H_{Q})) ∩ 𝔸_{k}^{n} =

Res_{𝔸_{k}^{n}}^{𝔸_{K}^{n}}(H_{Q} ∩𝔸_{K}^{n}) = V (s^{(1)}, …, s^{(n)}) = V (S^{(1)}, …, S^{(n)})∩𝔸_{k}^{n} as subschemes of 𝔸_{k}^{n}. □

4.5 Determination of non-zero-dimensional fibers

For the analysis of the algorithm we are interested in the number of points Q ∈ ℙ^{1}(K) for which the fiber X_{Q_{⊚}} = p_{2}^{−1}(Q_{⊚}) is not zero-dimensional. For this we first consider a base change to K, such that X_{K} is a closed subscheme of (ℙ_{K}^{1})^{n} × (ℙ_{K}^{1})^{n}, and we perform explicit computations in the Chow ring of (ℙ_{K}^{1})^{n}×(ℙ_{K}^{1})^{n}. We identify for notational reasons (ℙ^{1})^{n}×(ℙ^{1})^{n} componentwise with ∏_{i=1}^{n} Proj(ℤ[X_{1,i}, Y_{1,i}]) × ∏_{i=1}^{n} Proj(ℤ[X_{2,i}, Y_{2,i}]), and let h_{ℓ,i} be the class of X_{ℓ,i} in the Chow ring of (ℙ_{K}^{1})^{n} × (ℙ_{K}^{1})^{n}.

Lemma 4.19 The class of X_{K} in CH((ℙ_{K}^{1})^{n}×(ℙ_{K}^{1})^{n}) is 2^{(n−1)·n} ∏_{i=1}^{n}(h_{1,1}+ ⋯ + h_{1,n} + h_{2,i}).

Proof. X_{K} is defined inside (ℙ_{K}^{1})^{n} × (ℙ_{K}^{1})^{n} by the polynomials

F_{j} := S_{φ,n+1}(X_{1,1}, Y_{1,1}, …, X_{1,n}, Y_{1,n}, X_{2,j}, Y_{2,j})

for j = 1, …, n. One can easily see with this explicit description that for all ℓ = 2, …, n V (F_{1}, …, F_{ℓ−1}) meets V (F_{ℓ}) properly.

Indeed, let C be an irreducibility component of V (F_{1}, …, F_{ℓ−1}). Then C = C′ ×(ℙ_{K}^{1})^{n−ℓ+1} for some C′ ⊆ (ℙ_{K}^{1})^{n} ×(ℙ_{K}^{1})^{ℓ−1}. Let (Q_{1}, Q_{2}) ∈ C′(\overline{K}), where Q_{1} ∈ (ℙ^{1})^{n}(\overline{K}) and Q_{2} ∈ (ℙ^{1})^{ℓ−1}(\overline{K}). Now there are at most 2^{n−1} points in Q_{3} ∈ ℙ^{1}(\overline{K}) with F_{ℓ}(Q_{1}, Q_{3}) = 0. Choose some Q_{3} ∈ ℙ^{1}(\overline{K}) which is distinct from these points, and choose Q_{4} ∈ (ℙ^{1})^{n−ℓ}(\overline{K}) arbitrarily. Then (Q_{1}, Q_{2}, Q_{3}, Q_{4}) is a \overline{K}-valued point of C which does not lie in V (F_{ℓ})(\overline{K}).

By Axiom A7 on intersection theory in [Har77, Appendix A] we conclude that [X_{K}] = [V (F_{1})] ⋯ [V (F_{n})] in the Chow ring of (ℙ_{K}^{1})^{n} × (ℙ_{K}^{1})^{n}. Moreover, [V (F_{j})] = 2^{n−1}(h_{1,1} + ⋯ + h_{1,n} + h_{2,j}). This gives the statement. □

Lemma 4.20 The map (p_{2})_{|X} is surjective.

Proof. There are two possible ways to prove this statement:

First, by the previous lemma and Lemma 4.6 we have ((p_{2})_{K})_{∗}([X_{K}]) = n! · 2^{(n−1)·n}, thus (p_{2})_{K}(X_{K}) is equal to the ambient space ∏_{i=1}^{n} Proj(K[X_{2,i}, Y_{2,i}]).

Second, Let Q = (Q_{1}, …, Q_{n}) ∈ ∏_{i=1}^{n} Proj(K[X_{2,i}, Y_{2,i}])(\overline{K}). Then the geometric fiber X_{Q} is the subscheme of ∏_{i=1}^{n} Proj(\overline{K}[X_{1,i}, Y_{1,i}]) defined by F_{i}(X_{1,1}, Y_{1,n}, …, X_{1,n}, Y_{1,n}, Q_{i}) for i = 1, …, n. We see in particular that the fiber is never empty. More precisely, if it is zero-dimensional then its degree is n! · 2^{(n−1)·n}. □

Remark 4.21 From the fact that (p_{2})_{|X} is surjective one can easily deduce that the map a_{n} : V^{n} ⟶ Res_{k}^{K}(E) is also surjective.

Let now q_{i} : ∏_{i=1}^{n}(Proj(K[X_{1,i}, Y_{1,i}])) ⟶ Proj(K[X_{1,i}, Y_{1,i}]) be the projection to the i^{th} component.

For some Q ∈ ∏_{i=1}^{n}(Proj(K[X_{2,i}, Y_{2,i}]))(\overline{K}) the geometric fiber X_{Q} (which is contained in ∏_{i=1}^{n} Proj(\overline{K}[X_{1,i}, Y_{1,i}])) is zero-dimensional if and only if for no i = 1, …, n the image of X_{Q} under q_{i} is equal to Proj(\overline{K}[X_{1,i}, Y_{1,i}]).

Let R_{i} ∈ K[X_{1,i}, Y_{1,i}, X_{2,1}, Y_{2,1}, …, X_{2,n}, Y_{2,n}] be the multigraded resultant of F_{1}, …, F_{n} with respect to the variables X_{1,1}, Y_{1,1}, …, X_{1,i−1}, Y_{1,i−1}, X_{1,i+1}, Y_{1,i+1}, …, X_{1,n}, Y_{1,n}. Let Q = (Q_{1}, …, Q_{n}) ∈ ∏_{i=1}^{n} Proj(K[X_{2,i}, Y_{2,i}])(\overline{K}). Then q_{i}(X_{Q}) = Proj(\overline{K}[X_{1,i}, Y_{1,i}]) if and only if R_{i}(X_{i}, Y_{i}, Q_{1}, …, Q_{n}) = 0. Thus the geometric fiber X_{Q} is zero-dimensional if and only if for all i = 1, …, n R_{i}(X_{i}, Y_{i}, Q_{1}, …, Q_{n}) is non-trivial.

Note now that not all fibers are non-zero-dimensional because X has dimension n (see Lemma 4.13) and (ℙ_{K}^{1})^{n} has dimension n too. Thus the polynomials R_{1}, …, R_{n} are all non-trivial.

Lemma 4.22 Each polynomial R_{i} has multidegree (n! · 2^{(n−1)·n}, (n − 1)! · 2^{(n−1)·n}, …, (n − 1)! · 2^{(n−1)·n}).

Proof. The polynomials F_{1}, …, F_{n} have multidegree (2^{n−1}, …, 2^{n−1}) ∈ ℕ^{n−1} with respect to the variables under consideration. By Lemma 4.7 the corresponding generic resultant is homogeneous in the coefficients of each of the polynomials of degree (n − 1)! · 2^{(n−1)^{2}}. Now for j = 1, …, n, F_{j} has degree 2^{n−1} with respect to X_{2,j}, Y_{2,j}, and these variables do not occur in F_{ℓ} for ℓ ≠ j. This implies that the degree of R_{i} with respect to X_{2,j}, Y_{2,j} is (n − 1)! · 2^{(n−1)^{2}} · 2^{n−1} = (n − 1)! · 2^{(n−1)·n}. Moreover, each polynomial F_{ℓ} has degree 2^{n−1} with respect to X_{1,i}, Y_{1,i} and therefore the degree of R_{i} with respect to X_{1,i}, Y_{1,i} is (n − 1)! · 2^{(n−1)^{2}} · n · 2^{n−1} = n! · 2^{(n−1)·n}. □

Let us now for every i = 1, …, n fix some non-trivial coefficient C_{i} of R_{i} regarded as a polynomial in K[X_{2,n}, Y_{2,n}, …, X_{2,n}, Y_{2,n}][X_{1,i}, Y_{1,i}]. Then clearly the points Q ∈ ∏_{i=1}^{n} ∏ Proj(K[X_{2,i}, Y_{2,i}]) for which the fiber X_{Q} is not zero-dimensional are contained in

⋃_{i=1}^{n} V (C_{i}) ⊆ (ℙ_{K}^{1})^{n} .

Let us fix some i = 1, …, n. Then V (C_{i}) is an effective Cartier divisor of multidegree ((n−1)!·2^{(n−1)·n}, …, (n−1)!·2^{(n−1)·n}) in ∏_{i=1}^{n} Proj(K[X_{2,i}, Y_{2,i}]), and (p_{2})_{K}^{−1}(V (C_{i})) is an effective Cartier divisor of multidegree (0, …, 0, (n − 1)! · 2^{(n−1)·n}, …, (n − 1)! · 2^{(n−1)·n}) in (ℙ_{K}^{1})^{n} × (ℙ_{K}^{1})^{n}.

It follows that

\begin{matrix}[X_{K}] · [(p_{2})_{K}^{−1}(V (C_{i}))] = \\ (n − 1)! · 2^{2(n−1)·n} · (∏_{i=1}^{n}(h_{1,1} + ⋯ + h_{1,n} + h_{2,i})) · (h_{2,1} + ⋯ + h_{2,n}) \end{matrix}

in CH((ℙ_{K}^{1})^{n} × (ℙ_{K}^{1})^{n}). With Lemma 4.6 this implies that

\begin{aligned}& ((p_{1})_{K})_{∗}([X_{K}] · [(p_{2})_{K}^{−1}(V (C_{i}))]) \\ = & (n − 1)! · 2^{2(n−1)·n} · n · (h_{1,1} + ⋯ + h_{1,n}) \\ = & n! · 2^{2(n−1)·n} · (h_{1,1} + ⋯ + h_{1,n}) . \end{aligned}  (6)

Assumption 4.23 Let us from now on assume that Condition 2.7 is satisfied.

Notation 4.24 Let k = 𝔽_{q} (such that K = 𝔽_{q^{n}}).

Recall that X is now geometrically irreducible (Proposition 4.16). Clearly X_{K} is not contained in (p_{2})_{K}^{−1}(V (C_{i})) (because otherwise (p_{2})_{K}(X_{K}) would be contained in V (C_{i}), contradicting the surjectivity of p_{2}). Thus we have [X_{K}]·[(p_{2})_{K}^{−1}(V (C_{i}))] = [X_{K} ∩(p_{2})_{K}^{−1}(V (C_{i}))] by Axiom A7 on intersection theory in [Har77, Appendix A]. As the map (p_{1})_{K} : X_{K} ⟶ ∏_{i=1}^{n} Proj([X_{1,i}, Y_{1,i}]) is finite and flat (cf. Lemma 4.13), the dimension of (p_{1})_{K}(X_{K} ∩ C_{i}) is equal to the dimension of X_{K} ∩ C_{i}. With (6) we conclude:

Lemma 4.25 (p_{1})_{K}(X_{K} ∩ C_{i}) (with the induced reduced scheme structure) is a reduced effective Cartier divisor of ∏_{i=1}^{n} Proj([X_{1,i}, Y_{1,i}]) whose multidegree is componentwise ≤ (n! · 2^{2(n−1)·n}, …, n! · 2^{2(n−1)·n}).

The subscheme

⋃_{i=1}^{n} ⋃_{j=0}^{n−1} σ^{j}((p_{1})_{K}(X_{K} ∩ C_{i}))

of ∏_{i=1}^{n} Proj([X_{1,i}, Y_{1,i}]) is Gal(K|k)-invariant. It thus descends to a subscheme of (ℙ_{k}^{1})^{n}; let B be this scheme.

Lemma 4.26

a) B is a reduced effective Cartier divisor whose multidegree is componentwise ≤ (n^{2} · n! · 2^{2(n−1)·n}, …, n^{2} · n! · 2^{2(n−1)·n}). b) Let Q ∈ (ℙ^{1}(\overline{k}))^{n} − B(k), and let Q′ be any preimage of Q under p_{1}.

Then the fiber X_{p_{2}(Q′)} is zero-dimensional.

c) There are at most n^{3} · n! · 2^{2(n−1)·n} · (q + 1)^{n−1} points in B(k).

Proof. Let A_{i} be a multihomogeneous polynomial defining (p_{1})_{K}(X_{K} ∩ C_{i}). Then B is V (∏_{j=0}^{n−1} σ^{j}(A_{1} ⋯ A_{n}))^{red}. The polynomial in question has a multidegree which is componentwise ≤ (n^{2}·n!·2^{2(n−1)·n}, …, n^{2}·n!·2^{2(n−1)·n}).

Statement b) follows immediately from the definition of B.

Statement c) follows from a) and the following lemma. □

Lemma 4.27 Let H be an effective Cartier divisor of multidegree \underline{d} in (ℙ_{k}^{1})^{n}. Then

#H(k) ≤ (∑_{i=1}^{n} d_{i}) · (q + 1)^{n−1} .

Proof. It clearly suffices to show the result under the condition that all entries of the multidegree are positive.

We proceed with induction by n. For n = 1 the claim is that #H(k) ≤ d_{1}, and this is surely correct.

Now let H be defined by the polynomial F (X_{1}, Y_{1}, …, X_{n}, Y_{n}) ∈ k[X_{1}, Y_{1}, …, X_{n}, Y_{n}]. Let us consider the projection to the first n−1 components (ℙ_{k}^{1})^{n} ⟶ (ℙ_{k}^{1})^{n−1} and the induced morphism H ⟶ (ℙ_{k}^{1})^{n−1}. Now for every point P = (P_{1}, …, P_{n−1}) ∈ (ℙ_{k}^{1})^{n−1}(k) for which F (P_{1}, …, P_{n−1}, X_{n}, Y_{n}) does not vanish, the fiber has degree d_{n}, thus in particular it contains at most d_{n} k-rational points. Let now C be a non-trivial coefficient of F regarded as a polynomial in k[X_{1}, Y_{1}, …, X_{n−1}, Y_{n−1}][X_{n}, Y_{n}]. Then all points P ∈ (ℙ_{k}^{1})^{n−1}(k) for which F (P_{1}, …, P_{n−1}, X_{n}, Y_{n}) vanishes are contained in V (C). Now C has multidegree (d_{1}, …, d_{n−1}), and thus #V (C)(k) ≤ (∑_{i=1}^{n−1} d_{i}) · (q + 1)^{n−2} by induction. We conclude:

#H(k) ≤ d_{n} · (q + 1)^{n−1} + #V (C)(k) · (q + 1)
≤ d_{n} · (q + 1)^{n−1} + (∑_{i=1}^{n−1} d_{i}) · (q + 1)^{n−1}
= (∑_{i=1}^{n} d_{i}) · (q + 1)^{n−1}
□

Given an element P ∈ E(K), there is a φ-isolated decomposition of P if and only if the fiber X_{φ(P)_{⊚}} contains an isolated k-rational point (Q_{1}, …, Q_{n}) such that there exist P_{1}, …, P_{n} ∈ E(K) with φ(P_{i}) = Q_{i} and ∑_{i} P_{i} = P. This is in particular the case if the fiber is 0-dimensional and contains such a k-rational point.

We want to derive a lower bound on the number of such elements P ∈ E(K).

In [Die09], among other things we study the complexity of the elliptic curve discrete logarithm problem restricted to curves over extension fields with a fixed extension degree n. In preparation for this, we now proceed a bit more generally:

Given any subset M of { (P_{1}, …, P_{n}) ∈ E(K)^{n} | φ(P_{i}) ∈ ℙ^{1}(k) for all i = 1, …, n }, we want to derive a lower bound on the number of elements P ∈ E(K) such that the fiber X_{φ(P)_{⊚}} is zero-dimensional and contains a k-rational point (Q_{1}, …, Q_{n}) such that there exist P_{1}, …, P_{n} ∈ E(K) with φ(P_{i}) = Q_{i} and ∑_{i} P_{i} = P.

Let us for this consider the commutative diagram of sets of k-valued points

\xymatrix{G(k) \ar[r]^{ρ} & X(k) \ar[d]^{(p_{1})_{|X}} \\ V^{n}(k) \ar[u]^{γ} \ar[r]^{τ} & ∏_{i=1}^{n} Proj(k[X_{1,i}, Y_{1,i}])(k) ,}

where the map γ : V (k) ⟶ G(k) is induced by the graph morphism, that is, it is explicitly given by (P_{1}, …, P_{n}) ↦ (P_{1}, …, P_{n}, − ∑_{i} P_{i}), the map ρ : G(k) ⟶ X(k) is induced by the morphism G ⟶ X defined in Proposition 4.16, and the map τ : V^{n}(k) ⟶ ∏_{i=1}^{n} Proj(k[X_{1,i}, Y_{1,i}])(k) is induced componentwise by the canonical morphism in diagram (3).

Note that under the scalar restriction functor and in the context of the index calculus algorithm for the Theorem, V (k) corresponds to the factor base F = {P ∈ E(K) | φ(P) ∈ ℙ^{1}(k)}, G(k) corresponds to the set of tuples (P_{1}, …, P_{n}, P) with φ(P_{i}) ∈ ℙ^{1}(k) and P = − ∑_{i} P_{i}, and X(k) corresponds to the set of tuples (Q_{1}, …, Q_{n}, Q) with Q_{i} ∈ ℙ^{1}(k) and Q ∈ ℙ^{1}(K) and S_{n+1}(Q_{1}, …, Q_{n}, Q) = 0. The map γ corresponds then to the map which is again given by (P_{1}, …, P_{n}) ↦ (P_{1}, …, P_{n}, − ∑_{i} P_{i}), and the maps ρ and τ correspond to the componentwise application of φ.

Let M ⊆ {(P_{1}, …, P_{n}) ∈ E(K)^{n} | φ(P_{i}) ∈ ℙ^{1}(k) for all i = 1, …, n}, and let M_{⊚} be the corresponding subset of V^{n}(k). Then every element P ∈ E(K) such that φ(P)_{⊚} ∈ Res_{k}^{K}(ℙ_{K}^{1})(k) is the image under p_{2} of an element in (ρ∘γ)(M_{⊚})−p_{1}^{−1}(B(k)) is an element as desired. (Indeed, if P is such an element, first the fiber X_{φ(P)_{⊚}} is zero-dimensional by Lemma 4.26 b), and second there exist P_{1}, …, P_{n} ∈ M with φ(P_{1} + ⋯ + P_{n}) = φ(P), thus P_{1} + ⋯ + P_{n} = ±P.)

We are thus interested in the cardinality of the set

p_{2}((ρ ∘ γ)(M_{⊚}) − p_{1}^{−1}(B(k))) .

For this we first derive a lower bound on

(ρ ∘ γ)(M_{⊚}) − p_{1}^{−1}(B(k)) .

The image of this set in ∏_{i=1}^{n} Proj(k[X_{1,i}, Y_{1,i}])(k) is contained in

τ(M_{⊚}) − B(k) .

As τ corresponds to the componentwise application of φ, we have #τ(M_{⊚}) ≥ \frac{1}{2^{n}} #M_{⊚} = \frac{1}{2^{n}} #M.

With Lemma 4.26 c) we obtain:

\begin{aligned}& #((ρ ∘ γ)(M_{⊚}) − p_{1}^{−1}(B(k))) \\ ≥ & #(τ(M_{⊚}) − B(k)) \\ ≥ & \frac{#M}{2^{n}} − n^{3} · n! · 2^{2(n−1)·n} · (q + 1)^{n−1} . \end{aligned}  (7)

Now if an element Q in the set p_{2}((ρ∘γ)(V^{n}(k))−p_{1}^{−1}(B(k))) is given, the fiber of p_{2}(Q) under p_{2} is zero-dimensional, and thus its degree is n!·2^{(n−1)·n} (see the proof of Lemma 4.20). We therefore have the following proposition.

Proposition 4.28 Let

M ⊆ {(P_{1}, …, P_{n}) ∈ E(K)^{n} | φ(P_{i}) ∈ ℙ^{1}(k) for all i = 1, …, n} .

Then the number of elements P ∈ E(K) such that there exists a φ-isolated decomposition (P_{1}, …, P_{n}) of ±P with P_{1}, …, P_{n} ∈ M is

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

We now apply this proposition with M_{⊚} = V (k). By Proposition 4.11 for log_{2}(q) ≥ 7n and n ≥ 2 we have #V (k) ≥ \frac{q+1}{2}, thus #V^{n}(k) ≥ \frac{(q+1)^{n}}{2^{n}}. With Proposition 4.28 we obtain that the number of elements P ∈ E(K) such that there exist P_{1}, …, P_{n} ∈ E(K) with φ(P_{i}) ∈ ℙ^{1}(k) and ∑_{i} P_{i} = P is

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

Let now ϵ > 0. Then for n large enough this is

≥ \frac{q^{n−1}}{n! · 2^{n·(n+1)}} · (q − \frac{1}{2} · 2^{(2+ϵ)·n^{2}}) .

Then for log_{2}(q) ≥ (2 + ϵ) · n^{2} this is

≥ \frac{q^{n}}{n! · 2^{n·(n+1)+1}} .

Again for n large enough and log_{2}(q) ≥ (2 + ϵ) · n^{2} this is

≥ 2 · q^{n− \frac{1}{2}} .

We therefore have:

Proposition 4.29 Let ϵ > 0. Then for n large enough and (2 + ϵ) · n^{2} ≤ log_{2}(q) there are at least 2 · q^{n− \frac{1}{2}} elements in E(K) which have φ-isolated decompositions.

And this implies Proposition 2.9, the main result for the analysis of the decomposition algorithm in subsection 2.1.

References

[BLR80] S. Bosch, W. Lütkebohmert, and W. Raynaud. Néron Models. Springer-Verlag, 1980.

[Can90] J. Canny. Generalized characteristic polynomials. J. Symbolic Computation, 9:241–250, 1990.

[Die01] C. Diem. A study on theoretical and practical aspects of Weilrestrictions of varieties. PhD thesis, University of Essen, 2001.

[Die09] C. Diem. On the discrete logarithm problem in class groups of curves. Accepted for publication at Math. Comp., 2009.

[Ful84] W. Fulton. Intersection Theory. Springer-Verlag, 1984.

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

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

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

[Gro61] A. Grothendieck. Eléments de Géométrie Algébrique III, Première Partie. Publication Mathématiques, 11, 1961.

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

[KR89] E. Kani and M. Rosen. Idempotent relations and factors of Jacobians. Math. Ann., 284:307–327, 1989.

[LP92] H.W. Lenstra and C. Pomerance. A rigorous time bound for factoring integers. J. Amer. Math. Soc., 5, 1992.

[Mat89] H. Matsumura. Commutative Ring Theory. Cambridge University Press, 1989.

[Mil04] V. Miller. The Weil Pairing and Its Efficient Computation. J. Cryptology, 17:235–261, 2004.

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

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

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

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

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

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

Claus Diem Universität Leipzig Mathematisches Institut Johannisgasse 26 04103 Leipzig Deutschland diem@math.uni-leipzig.de