David Lubicz

Damien Robert

Computing Isogenies Between Abelian Varieties

We describe an efficient algorithm for the computation of separable isogenies between abelian varieties represented in the coordinate system given by algebraic theta functions. Our algorithm decomposes in two principal steps. First, from the knowledge of a subgroup K isotropic for the Weil pairing of an abelian variety A, we explain how to compute the theta null point corresponding to the quotient abelian variety A/K. Second, from the knowledge of the theta null point of A/K, we give an algorithm to obtain a rational expression for the isogeny from A to A/K. The algorithm resulting as the combination of these two steps can be viewed as a higher dimensional analog of the well known algorithm of Vélu to compute isogenies between elliptic curves.

In order to improve the efficiency of our algorithms, we introduce a compressed representation that allows to encode a point of level 4ℓ of a g dimensional abelian variety using only g (g +1)/2•4 g coordinates. We also give formulas to compute the Weil and commutator pairings given input points in theta coordinates. All the algorithms presented in this paper work in general for any abelian variety defined over a field of odd characteristic.

List of Notations

Notation Description Page List Z(n) g /n g n
The moduli space of theta null points of level n. A k (A k , , Θ A k ) is a polarized abelian variety with a theta structure of level ℓn.

B k (B k , 0 , Θ B k ) is an abelian variety ℓ-isogenous to A k with a theta structure of level n.

ϑ i (ϑ i ) i ∈Z(ℓn) are the canonical projective coordinates on A k

given by the theta structure.

0 A k The theta null 0 A k = ϑ i (0 A k ) i ∈Z(ℓn) . 0 B k
The theta null 0

B k = ϑ i (0 B k ) i ∈Z(n) . G( )
The Theta group of (A k , ) K( ) K( ) = K 1 ( )⊕K 2 ( ) is the decomposition of the kernel of the polarization induced by the Theta structure Θ A H (δ)

The Heisenberg group of type δ. s K( )

The natural section K( ) → G( ) induced by the Theta structure.

ρ

The affine action of G( ) on A k .

A k

The affine cone of A k .

B k

The affine cone of B k . ϑ i ( ϑ i ) i ∈Z(ℓn) are the affine coordinates on A k .

0 B k An affine lift of 0 B k . 0 A k
The affine lift of 0 A k such that π(

0 A k ) = 0 B k . π
The ℓ-isogeny π : A k → B k . π π( ϑ i ( x) i ∈Z(ℓn) ) = ϑ i ( x) i ∈Z(n) is the affine lift of π to A k → B k .

π i π i = π • (1, i, 0) = ϑ i + j (•) j ∈Z(n) . P i P i = (1, i, 0). 0 A k = (ϑ i + j ( 0 A k )) j ∈Z(ℓn) .
R i R i = π i ( 0 A k ) = π( P i ). (e 1 , . . . , e g )

A basis of Z(ℓn) (d 1 , . . . , d g )

d i = ne i = Z(ℓ) (When ℓ ∧ n = 1) S S = {d 1 , d 2 , . . . , d g , d 1 + d 2 , . . . d 1 + d g , d 2 + d 3 , . . . d g -1 + d g } (When ℓ ∧ n = 1) e ℓ 0
The extended commutator pairing on

B k [ℓ] e W
The Weil pairing.

〈•, •〉

The canonical pairing on Z(n) × Ẑ(n).

Glossary

 Introduction

The general problem of computing separable isogenies between abelian varieties splits into different computational sub-problems depending on the expected input and output of the algorithm. These problems are:

• Given an abelian variety A k over a field k and an abstract finite abelian group K compute all the abelian varieties B k such that there exists an isogeny A k → B k whose kernel is isomorphic to K, and give rational expressions for the corresponding isogenies.

• Given an abelian variety A k and a finite subgroup K of A k , recover the quotient abelian variety B k = A k /K as well a rational expression for an isogeny A k → B k .

• Given two isogenous abelian varieties, A k and B k , compute a rational expression for an isogeny

A k → B k .
In the present paper, we are concerned with the first two problems. In the case that the abelian variety is an elliptic curve, efficient algorithms have been described that solve all the aforementioned problems [Ler]. In particular, an algorithm proposed by Vélu [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF] takes as input a finite subgourp G of cardinal ℓ of an elliptic curve E k , and returns the equation of the quotient E k /G at the cost of O(ℓ) additions in E k . The algorithm of Vélu also gives a rational expression for the isogeny E k → E k /G in the coordinate system provided by the Weierstrass form of the elliptic curves. For higher-dimensional abelian varieties much less is known. Richelot's formulas [START_REF] Richelot | Essai sur une méthode générale pour déterminer la valeur des intégrales ultra-elliptiques, fondée sur des transformations remarquables de ces transcendantes[END_REF][START_REF] Richelot | De transformatione Integralium Abelianorum primiordinis commentation[END_REF] can be used to compute (2, 2)-isogenies between abelian varieties of dimension 2. The paper [START_REF] Smith | Isogenies and the discrete logarithm problem in jacobians of genus 3 hyperelliptic curves[END_REF] also introduces a method to compute certain isogenies of degree 8 between jacobian of curves of genus three. In this paper, we present an algorithm to compute (ℓ, . . . , ℓ)-isogenies between abelian varieties of dimension g represented in the coordinate system provided by algebraic theta functions for any ℓ 2 and g 1 when the characteristic of k is odd and relatively prime to ℓ.

Let n ∈ be such that 2|n and n 4. Let n = (n, n, . . . , n) ∈ g , and Z(n) = g /n g . We denote by n the modular space of marked abelian varieties (A k , , Θ A k ) where is a totally symmetric ample line bundle on A k and Θ A k is a symmetric theta structure of type Z(n) for (see [Mum66, sec. 2]). In the following, we will also call a theta structure of type Z(n) a theta structure of level n. The modular space n is well-suited for computing modular correspondences since the algebraic systems which play the same role in this space as the classical modular polynomials have their coefficients in {1, -1}, and as a consequence are much more amenable to computations than their counterparts using the j -invariant in genus 1 or the Igusa invariants in genus 2 . In the article [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF], we have defined a modular correspondence:

ϕ : ℓn → n × n , (a i ) i∈Z(ℓn) → ((a i ) i ∈Z(n) , ( j ∈Z(ℓ) a i+n j ) i ∈Z(n) )
for ℓ ∈ * prime to n, which can be seen as a generalization of the classical modular correspondence X 0 (ℓ) → X 0 (1) × X 0 (1) for elliptic curves (see for instance [START_REF] Kohel | The AGM-X 0 (N ) Heegner point lifting algorithm and elliptic curve point counting[END_REF]). To explain it, let p 1 and p 2 be respectively the first and second projections n × n → n , and let ϕ 1 = p 1 • ϕ, ϕ 2 = p 2 • ϕ. The map ϕ 1 : ℓn → n is such that (x, ϕ 1 (x)) for x ∈ ℓn (k) are modular points corresponding to ℓ-isogenous abelian varieties.

Introduction

In fact, consider (a i ) i ∈Z(ℓn) ∈ ϕ -1 1 ((b i ) i∈Z(n) ). The modular point (a i ) i ∈Z(ℓn) defines a triple (A k , , Θ A k ) and the classical isogeny theorem for algebraic theta functions [START_REF] Mumford | On the equations defining abelian varieties[END_REF]th. 4] gives an explicit isogeny π : A k → B k . We denote by π : B k → A k the isogeny that makes the following diagram commutative:

y ∈ B k z ∈ A k x ∈ A k π π [ℓ]
The main result of this paper is: Theorem 1.1: Let B k be a dimension g marked abelian variety. Let (T 1 , . . . , T g ) ⊂ B k [ℓ] be a basis of a maximal subgroup K of B k [ℓ] isotropic for the Weil pairing. Let π : B k → B k /K be the corresponding isogeny. One can compute the compressed coordinates of the modular point (a i ) i ∈Z(ℓn) corresponding to π with O(log(ℓ)) addition chains in B k and O(1) ℓ t h -roots of unity extractions.

Once we have (a i ) i ∈Z(ℓn) , we can compute the compressed coordinates of the image of a point in B k by π

with O(log(ℓ)) addition chains in B k . Taking the generic point of B k , we obtain in particular a rational expression for the isogeny π.

The precise meaning of addition chain and compressed coordinates will be made clear in the course of the paper. A proof of this theorem is given in Section 4.2 and Section 5.1. It should be remarked that this result constitute a higher dimensional analog of the classical Vélu's algorithm since by combining the two conclusions of the theorem, we obtain an efficient algorithm which takes as input an abelian variety B k and a maximal subgroup K of B k [ℓ] isotropic for the Weil pairing and computes a rational expression for the isogeny B k → B k /K. Note that the classical isogeny theorem for theta functions is not sufficient for our purpose of computing isogenies between abelian varieties. Although it is effective, the isogeny theorem can only be used to compute isogenies from a marked abelian variety of level ℓ to a marked abelian variety of level n where n divides ℓ, so it only provides us with a way to compute isogenies by "going down" in the level of the theta structure. At some point, we need a way to compute isogenies by "going up" the level and this is precisely what gives Theorem 1.1. We can then combine the two theorems: once we have computed an isogeny π : B k → A k , it is possible to compose π with an isogeny π 2 : A k → C k given by the isogeny theorem such that π 2 • π is an ℓ 2 -isogeny (see [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF]Sec 3] or Section 2.2). In fact, let C k be the abelian variety associated to the modular point

(c i ) i∈Z(n) = ϕ 2 (a i ) i∈Z(ℓn) then we have the following diagram B k A k B k C k [ℓ] π π π 2
The isogeny π 2 • π is then an ℓ 2 isogeny between B k and C k which are two marked abelian varieties with a theta structure of level n. Possible applications of our algorithm includes:

• The transfer the discrete logarithm from an abelian variety to another abelian variety where the discrete logarithm is easy to solve [START_REF] Smith | Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves[END_REF] • The computation of isogeny graphs to obtain a description the endomorphism ring of an abelian variety.

• The computation of Hilbert class polynomials.

We end up the introduction with some general remarks about the algorithms presented in this paper. The assumption that n is prime to ℓ is inessential. There is nonetheless one noticeable difference if we drop this hypothesis. Suppose that we are given B k [ℓ]. Since B k is given by a theta structure of level n, we can recover B k [n] using the action of the theta group on the theta null point

(b i ) i ∈Z(n) . If ℓ is prime to n, this gives us B k [ℓn],
and we can use the first assertion of Theorem 1.1 to obtain a modular point of type Z(ℓn). If ℓ is not prime to n, we have to compute B k [ℓn] directly.

Although we only consider the case of (ℓ, . . . , ℓ)-isogeny, it is also possible to compute more general types of isogenies with our algorithm. With the notations of Section 2, let δ 0 = (δ 1 , . . . , δ g ) be a sequence of integers such that 2|δ 1 and δ i |δ i +1 , and let (b i ) i ∈Z(δ 0 ) ∈ δ 0 be a modular point corresponding to an abelian variety B k . Let δ ′ = (ℓ 1 , . . . , ℓ g ) (where ℓ i |ℓ i+1 ) and define δ = (δ 1 ℓ 1 , . . . , δ g ℓ g ). Let (a i ) i∈Z(δ) ∈ δ be such that ϕ 1 (a i ) i ∈Z(δ) = (b i ) i ∈Z(δ 0 ) where ϕ 1 is the natural inclusion of Z(δ 0 ) into Z(δ). The theta null point (a i ) i ∈Z(δ) corresponds to an abelian variety A k , such that there is a (ℓ 1 , • • • , ℓ g )-isogeny π : A k → B k , which can be computed by the isogeny theorem [Mum66, Th. 4] (see Section 2.2). The isogeny we compute in Step 2 is the contragredient isogeny π :

B k → A k of type (ℓ g /ℓ 1 , ℓ g /ℓ 2 , • • • , 1, ℓ g , ℓ g , • • • , ℓ g ).
Using the modular correspondence ϕ 1 to go back to a modular point of type Z(δ 0 ) (see Section 1) gives an isogeny of type

(ℓ g /ℓ 1 , ℓ g /ℓ 2 , • • • , 1, ℓ 1 ℓ g , ℓ 2 ℓ g , • • • , ℓ g ℓ g ).
For the clarity of the exposition, we will stick to the case δ 0 = n and δ = ℓn and we leave to the reader the easy generalization.

For an actual implementation, we want to use the smallest n possible to get a compact representation of the points and a fast addition chain. In fact it is possible to tweak Theorem 1.1 to make it works with the case n = 2. This case is very important in practice: it allows a more compact representation of the points than for n = 4 (we gain a factor 2 g in space), a faster addition chain (see Section 4.1.1), but most importantly it reduces the most consuming part of our algorithm, the computation of the points of ℓ-torsion, since there are half as much such points on the Kummer variety associated to an abelian variety. For each algorithm that we use, we give an explanation on how to adapt it for the type Z(2) case: see Section 3.2.1 and the end of Sections 4.2, 5.1, 5.3 and 6.2.

The paper is organized as follow. In Section 2, we recall the isogeny theorem and we study the relationship between isogenies and the action of the theta group. We recall the addition relations, which play a central role in this paper in Section 3. We then explain how to compute the isogeny associated to a modular point in Section 4. If the isogeny is given by theta functions of type Z(4ℓ), it requires (4ℓ) g coordinates. We give a point compression algorithm in Section 4.1, showing how to express such an isogeny with only g (g +1)/2•4 g coordinates. In Section 5 we give a full generalization of Vélu's formulas that constructs an isogenous modular point with prescribed kernel. This algorithm is more efficient than the special Gröbner basis algorithm from [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF]. There is a strong connection between isogenies and pairings, and we use the above work to explain how one can compute the commutator pairing and how it relates to the usual Weil pairing in Section 6.

 Modular correspondences and theta null points

In this section, we fix some notations that we use in the rest of the paper. In Section 2.1, we recall the definition of a theta structure and the projective embedding [Mum66, Sec. 1] deduced from it. In Section 2.2 we recall the isogeny theorem, which relate the theta functions of two isogenous abelian varieties with compatible theta structures. In Section 2.3 we study the connection between isogenies and the action of the theta group on the affine cone of the projective embedding given by the theta structure.

Let A k be an abelian variety of dimension g over a perfect field k and denote by K(A k ) its function field. An isogeny is a finite surjective map of abelian varieties π : A k → B k and is said to be separable if the function field K(A k ) is a finite separable extension of K(B k ). A separable isogeny is uniquely determined by its kernel, which is a finite subgroup of A k (k). In that case, the cardinality of the kernel is the degree of the isogeny. Since we will only consider isogenies of degree prime to the characteristic of k, we will only deal with separable isogenies. In the rest of this paper, by ℓ-isogeny for ℓ > 0, we always mean a (ℓ,

• • • , ℓ)-isogeny where (ℓ, • • • , ℓ) ∈ g .

. Theta structures

Let A k be a g dimensional abelian variety over a perfect field k. Let be an ample totally symmetric line bundle of degree d on A k . We suppose moreover that d is prime to the characteristic of k. Denote by K( ) the kernel of the isogeny ϕ : A k → Âk , defined on geometric points by x → τ * x ⊗ -1 where τ x is the translation by x. Let δ = (δ 1 , . . . , δ g ) be the sequence of integers satisfying δ i |δ i+1 such that, as group schemes K( ) ≃ g i=1 ( /δ i ) 2 k . We say that δ is the type of . In the following we let Z(δ) = g i=1 ( /δ i ) k , Ẑ(δ) be the Cartier dual of Z(δ), and

K(δ) = Z(δ) × Ẑ(δ). If x ∈ Z(δ) and ℓ ∈ Ẑ(δ), we denote 〈x, ℓ〉 := ℓ(x).
Let G( ) and (δ) be respectively the theta group of (A k , ) and the Heisenberg group of type δ [Mum66, p. 294]. In this article, elements of G( ) will be written as (x, ψ x ) with x ∈ K( ) and ψ x : → τ * x is an isomorphism. We know that G( ) and (δ) are central extensions of K( ) and K(δ) by the multiplicative group m,k . By definition, a theta structure Θ A k on (A k , ) is an isomorphism of central extensions from (δ) to G( ). We denote by e the commutator pairing [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 203] on K( ) and by e δ the canonical pairing on K(δ) = Z(δ) × Ẑ(δ). We recall that if (x 1 , x 2 ) and (y 1 , y 2 ) are in K(δ) we have e δ ((x 1 , x 2 ), (y 1 , y 2 )) = 〈x 1 , y 2 〉/〈y 1 , x 2 〉. We remark that a theta structure Θ A k induces a symplectic isomorphism Θ A k from (K(δ), e δ ) to (K( ), e ). Let K( ) = K 1 ( ) × K 2 ( ) be the decomposition into maximal isotropic subspaces induced by Θ A k .

The section K(δ) → (δ) defined on geometric points by (x, y) → (1, x, y) can be transported by the theta structure to obtain a natural section s K( ) : K( ) → G( ) of the projection κ : G( ) → K( ). We note s K 1 ( ) (resp. s K 2 ( ) ) the restriction of this section to K 1 ( ) (resp. K 2 ( )).

Recall [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 291] that a level subgroup K of G( ) is a subgroup such that K is isomorphic to its image by κ.

Let V = Γ(A k , ).
There is an action of the theta group G( ) on V by v → ψ -1 x τ * x (v) for v ∈ V and (x, ψ x ) ∈ G( ). This action can be transported via Θ A k to an action of (δ) on V . It can be shown that there is a unique (up to a scalar factor) basis (ϑ i ) i∈Z(δ) of V such that this action is given by:

(α, i , j ).ϑ Θ A k h = α.〈-i -h, j 〉.ϑ Θ A k h+i .
(

) 1
If there is no ambiguity, in this paper, we will sometimes drop the superscript Θ A k in the notation

ϑ Θ A k k .
This basis gives a projective embedding

ϕ Θ A k : A k → d -1 k which is uniquely defined by the theta structure Θ A k . The point (a i ) i ∈Z(δ) = ϕ Θ A k (0 A k ) is
χ (t )ϑ x+u+t ϑ x-u+t . t ∈Z(2) χ (t )a y+v+t a y-v+t . (2)
The data of a triple (A k , , Θ A k ) is called a marked abelian variety of type Z(δ). We denote by δ the quasi-projective variety defined as the locus of all theta null points associated to marked abelian varieties of type Z(δ). We recall [Kem89, Th. 28] that if n > 4, then n is an open subset in the projective variety described by the following equations in (k(Z(n))):

t ∈Z(2) χ (t )a x+t a x+t . t ∈Z(2) χ (t )a u+t a u+t = t ∈Z(2) χ (t )a z-x+t a z-y+t . t ∈Z(2) χ (t )a z-u+t a z-v+t a x = a -x
(3) for all x, y, u, v, z ∈ Z(n), such that x + y + u + v = 2z and all χ ∈ Ẑ(2).

. Isogenies compatible with a theta structure Let (a i ) i ∈Z(δ) ∈ δ be a theta null point associated to a triple (A k , , Θ A k ). Let δ 0 ∈ g be such that 4|δ 0 |δ, and write δ = δ 0 • δ ′ . In the following we consider Z(δ 0 ) as a subgroup of Z(δ) via the map ϕ :

(x i ) i ∈[1..g ] ∈ Z(δ 0 ) → (δ ′ i x i ) i ∈[1.
.g ] ∈ Z(δ). From now on, when considering Z(δ 0 ) ⊂ Z(δ), we always refer to this map. Let K ⊂ K( ) be any isotropic subgroup for e such that we can write

K = K 1 × K 2 with K i ⊂ K i ( ).
Let B k = A k /K and π : A k → B k be the associated isogeny. Since K is isotropic, K := s K( ) (K) is a level subgroup, so by Grothendieck descent theory there exists a polarization 0 on B k and an isomorphism

≃ π * K ( 0 ). The theta group G( 0 ) is isomorphic to ( K)/ K where ( K) is the centralizer of K in G( ) [Mum66, Prop. 2]. We say that a theta structure Θ B k on (B k , 0 ) is π-compatible with Θ A k if it
respects this isomorphism. The isogeny theorem ([Mum66, Th. 4]) then gives a way to compute (π * (ϑ

Θ B k i )) i ∈Z(n) given (ϑ Θ A k i ) i ∈Z(ℓn) . Note Θ -1 A (K) = Z 1 × Z 2 , we call Z 1 × Z 2 the type of π. If Z 1 = 0 we say that π is of type 1, and if Z 2 = 0 that π is of type 2. We note Z ⊥ 1 = {x ∈ Z(δ) | 〈x, Z 2 〉 = 1}.
Then there is a bijection between π-compatible theta structures on (B k , 0 ) and isomorphisms σ : [START_REF] Mumford | On the equations defining abelian varieties[END_REF]Th 4]). Since we are mainly interested with ℓ-isogenies, we now specialize to the case δ = ℓn, δ ′ = ℓ so that δ 0 = n. We take Proposition 2.2 (Isogeny theorem for compatible theta structures): Let (a i ) i ∈Z(ℓn) be a theta null point associated to a triple (A k , , Θ A k ) and (b i ) i ∈Z(n) a theta null point associated to (B k , 0 , Θ B k ). Let ϕ : Z(n) → Z(ℓn) be the canonical embedding. Then (b i ) i ∈Z(δ ′ ) = ϕ 1 (a i ) i∈Z(δ ′ ) if and only if there is an ℓ-isogeny π of type 1 such that Θ B k is π-compatible with Θ A k . In this case, let (ϑ

Z ⊥ 1 /Z 1 → Z(δ 0 ) (see
K = A k [ℓ] 2 , we then have Z 1 = 0, Z 2 = Ẑ(ℓ) ⊂ Ẑ(ℓn) so that π : A k → B k is an ℓ-isogeny of type 1. In this case we have Z ⊥ 1 = Z(n) ⊂ Z(
Θ A k i ) i∈Z(ℓn) (resp. (ϑ Θ B k i ) i ∈Z(n)
) be the canonical basis of (resp. 0 ) associated to Θ A k (resp. Θ B k ). There exists some ω ∈ k * such that for all i ∈ Z(n)

π * K (ϑ Θ A k i ) = ωϑ Θ B k ϕ(i ) . (4)
It is easy to describe ℓ-isogenies of type 2 from Proposition 2.2. In fact, let I 0 be the automorphism of the Heisenberg group (ℓn) that permutes Z(ℓn) and Ẑ(ℓn): I 0 (α, x, y) = (α, y, x). We define

I A k = Θ A k •I 0 •Θ -1 A k
, where I A k is the automorphism of the Theta group of A k that permutes K 1 ( ) and K 2 ( ). (There is a similar automorphism I B k of the theta group of B k ; we will usually note these automorphisms I since the theta group is clear from the

context.) If π 2 is a compatible isogeny of type 2 between (A k , , Θ A k ) and (B k , 0 , Θ B k ), then π 2 is a compatible isogeny of type 1 between (A k , , I A k • Θ A k ) and (B k , , I B • Θ B k ). Since the action of I is given by [FLR09, Section 5] ϑ I A k •Θ A k i = j ∈ Ẑ(ℓn) e(i , j )ϑ Θ A k j , (5)
we see that we have for all i ∈ Z(n)

π * (ϑ Θ B k i ) = j ∈Z(ℓ) ϑ Θ A k i+n j . (6)
Applying Equations ( 4) and (6) to 0 A k yields the formulas for the modular correspondence ϕ :

ℓn → n × n from Section 1.
. The action of the theta group on the affine cone and isogenies

Let π : (A k , , Θ A k ) → (B k , 0 , Θ B k
) be an ℓ-isogeny of type 1 between compatible theta structures. The action by translation ρ from K( ) on A k descends to an action on B k : if x ∈ K( ), the induced action on B k is simply the translation by π(x). The situation is more interesting if we consider the action of G(

). Since G( ) is a central extension of K( ) by m,k it is natural to let G( ) act on a central extension of A k by m,k More precisely, let V = Γ(A k , ) and let p k (V ) : k (V ) → k (V ) be the canonical projection. Let A k = p -1 k (V ) (A k ) be the affine cone of A k which is a central extension of A k by m,k
The action of G( ) on V given by (1), induces an action ρ on A k . This action is compatible with the action of K( ) on A k in the following way:

if κ : G( ) → K( ) is the projection, p k (V ) • ρ = ρ • κ. Similarly we note B k the affine cone of B k and ρ 0 the action of G( 0 ) on B k .
We say that a coordinate system ( ϑ

Θ A k i
) i∈Z(ℓn) on A k lifts the projective system (ϑ

Θ A k i ) i ∈Z(ℓn) on
A k if for all j ∈ Z(ℓn), on the principal open set defined by ϑ

Θ A k j , we have p * k (V ) (ϑ Θ A k i /ϑ Θ A k j ) = ϑ Θ A k i / ϑ Θ A k j
. Obviously, such a coordinate system ( ϑ i ) i∈Z(ℓn) is defined up to an action of m,k and we fix such a choice for the rest of the paper. In the same manner, we denote by ( ϑ

Θ B k i ) i ∈Z(n) a coordinate
system on B k that lifts the coordinate system (ϑ

Θ B k i
) i∈Z(n) . We will usually replace ( ϑ

Θ A k i ) i ∈Z(ℓn) (resp. ( ϑ Θ B k i ) i∈Z(n) ) by ( ϑ i ) i ∈Z(ℓn) (resp. ( ϑ i ) i∈Z(n) ) when no confusion is possible.
Since is symmetric, there is an action of the morphism [-1] on V given by f ∈ V → Φ(ι * f ) where ι : A → A maps x to -x and Φ is the normalized isomorphism ι * → . This action extends to an action on A k that we denote also by

[-1] : x ∈ A k (k) → -x. Now since G( ) is a symmetric theta structure we have [-1] * ϑ i = ϑ -i [Mum66, p. 331] so if x = ( x i ) i ∈Z(ℓn) then -x = ( x -i ) i ∈Z(ℓn) . Let π : A k → B k be the morphism such that π * ( ϑ Θ B k i ) = ϑ Θ A k i for i ∈ Z(n).
Note that π is just a lift to the affine cone of the isogeny π : A k → B k , so that the following diagram commutes:

A k A k B k B k p A k p B k π π
We call π the lift of π compatible with the choice of affine coordinates on A k and B k .

We will now study the link between the action ρ of G( ) on A k and the morphism π. To simplify the notations, if (α, i, i) ∈ (δ) and x is a geometric point of A k , we will note (α, i, j ). x :

= ρ (Θ A k ((α, i, j ))). x. Let K π = Θ A k ( Ẑ(ℓ)) be the kernel of the isogeny π : A k → B k and recall (see Section 2.2) that G( 0 ) = ( K π )/ K π . Proposition 2.3: Let g ∈ ( K π ) and note g its image in ( K π )/ K π . We have ρ 0 (g ) = π • ρ (g )
. Proof: This is an immediate consequence of the fact that the two theta structures Θ A k and Θ B k are π-compatible.

For i ∈

(ℓn), we can define a mapping π i :

A k → B k given on geometric points by x → π( ρ (Θ A k (i)). x). If Θ A k (i ) ∈ ( K π ), Proposition 2.3 shows that π i = ρ 0 (Θ A k (i )) • π, hence π i can be recovered from π and the action ρ 0 . Since ( K π ) ⊃ s K( ) (K 2 ( ))
, the interesting mappings to study are then π i := π (1,i,0) for i ∈ Z(ℓn). They are given on geometric points by

π i (( ϑ j ( x)) j ∈Z(ℓn) ) = ( ϑ i +ℓ. j ( x)) j ∈Z(n) .
Corollary 2.4: Keeping the notations from above, we have 1. Let be a subset of Z(ℓn), such that

+ Z(n) = Z(ℓn). Then x ∈ A k (k) is uniquely determined by { π i ( x)} i ∈ . 2. Let y ∈ A k (k) be such that π( y) = π( x). Then there exists j ∈ Ẑ(ℓ) ⊂ Ẑ(ℓn) such that y = (1, 0, j ). x and π i ( y) = e ℓn (i , j ) π i ( x).
In particular π i ( y) and π i ( x) differ by an ℓ t h -root of unity.

Proof:

1. Since π i (( ϑ j ( x)) j ∈Z(ℓn) ) = ( ϑ i+ℓ. j ( x)) j ∈Z(n) , from { π i ( x)} i ∈ one can obtain the values ϑ j ( x) j ∈ +Z(n) . If + Z(n) = Z(ℓn) this shows that we can recover x = ( ϑ j ( x)) j ∈Z(ℓn) . 2. If π( y) = π( x), then p A k ( y) -p A k ( x) ∈ K π . So there exists j ∈ Ẑ(ℓ) and α ∈ k * such that y = (α, 0, j ). x. Hence ϑ i ( y) = αe ℓn (i , j ) ϑ i ( x). Since π( x) = π( y), α = 1. Moreover, as j ∈ Ẑ(ℓ), e ℓn (i + k, j ) = e ℓn (i, j ) if k ∈ Z(n) so that π i ( x) = e ℓn (i, j ) π i ( y).
Corollary 2.4 shows that ρ descends to an action on B k /µ k (ℓ) where µ k (ℓ) is the group scheme of ℓ-roots of unity on k.

Example 2.5:

• If ℓ is prime to n, the canonical mappings Z(n) → Z(ℓn) and Z(ℓ) → Z(ℓn) induce an isomorphism Z(n) × Z(ℓ) ∼ → Z(ℓn)
, and one can take = Z(ℓ) in Corollary 2.4.

• If ℓ is not prime to n, a possible choice for is

= { i ∈[1..g ] λ i e i |λ i ∈ [0..ℓ -1]}.

 The addition relations

In this section we study the addition relations and introduce the notion of addition chain on the affine cone of an abelian variety. These addition chains will be a basic tool for the isogeny computation algorithm presented in Section 4 and Vélu's like formulas of Section 5. In Section 3.1 we use the action of G( ) on the affine cone and the canonical lift s K( ) : K( ) → G( ) to introduce some canonical affine lifts on the affine cone. In Section 3.2 we prove in the framework of Mumford's theory a particular presentation of the Riemann relations, and we deduce from them the addition relations. In Section 3.3 we use the results of Section 2.3 to study the properties of the addition chain.

. The canonical lift of the action of K( ) to the affine cone

For the rest of this article we suppose that we are given a modular point (b i ) i ∈Z(n) corresponding to a triple (B k , 0 , Θ B k ). We choose a coordinate system ( ϑ

Θ B k i ) i ∈Z(n) on B k and a 0 B k ∈ p -1 B k (0 B k ). We remark that a choice of 0 B k ∈ p -1 B k (0 B k ) ⊂ B k
is nothing but a choice of an evaluation isomorphism: ϵ 0 : (0) ≃ k. In this Section and Section 4 we also suppose that we are given a modular point

(a i ) i∈Z(ℓn) corresponding to a triple (A k , , Θ A k ) such that ϕ 1 ((a i ) i ∈Z(ℓn) ) = (b i ) i ∈Z(n)
where ϕ 1 : ℓn → n is the modular correspondence introduced in Section 1. By Proposition 2.2 we then have an ℓ-isogeny π of type 1 between A k and B k . We choose a coordinate system ( ϑ

Θ A k i ) i∈Z(ℓn) on
A k and we denote by

0 A k the unique point in p -1 A k (0 A k ) such that 0 B k = π( 0 A k ) where π is given by π * ( ϑ Θ B k i ) = ϑ Θ A k i for i ∈ Z(n).
We recall that the theta structure Θ A k define a section s K( ) : K( ) → G( ), so that the map

x ∈ K( ) → s K( ) (x). 0 A k ∈ A k induces a section K( ) → A k of the map p A k : A k → A k . (More
generally this give a canonical section of the action by translation of K( ) on A k to an action on A k ). 13 Thus, once we have chosen 0 A k , we have a canonical way to fix an affine lift for any geometric point in K( ). For i ∈ Z(ℓn), let P i = (1, i, 0). 0 A k , and for j ∈ Ẑ(ℓn), let Q j = (1, 0, j ). 0 A k . We also put

R i = π( P i ) = π i ( 0 A k ), and R i = p B k ( R i ).
We remark that {R i } i∈Z(ℓ) is the kernel K π of π which explains the important role the points R i will play in the rest of this paper.

. The general Riemann relations

The Riemann relations (3) for ℓn and the Riemann equations (2) for A k are all particular case of more general Riemann relations, which we will use to get the addition relations on A k . An analytic proof of (a partial fourier transform) of these relations can be found in [Igu72, Th.1 p. 137].

Theorem 3.1 (Generalized Riemann Relations):

Let (A k , , Θ A k ) ∈ n and we suppose that 2|n. Let x 1 , y 1 , u 1 , v 1 , z ∈ A k (k) be such that x 1 + y 1 + u 1 + v 1 = 2z. Let x 2 = z -x 1 , y 2 = z -y 1 , u 2 = z -u 1 and v 2 = z -v 1 . Then there exist x 1 ∈ p -1 A k (x 1 ), y 1 ∈ p -1 A k (y 1 ), u 1 ∈ p -1 A k (u 1 ), v 1 ∈ p -1 A k (v 1 ), x 2 ∈ p -1 A k (x 2 ), y 2 ∈ p -1 A k (y 2 ), u 2 ∈ p -1 A k (u 2 ), v 2 ∈ p -1 A k (v 2
) that satisfy the following relations: for any i , j , k, l , m ∈ Z(ℓn) such that

i + j + k + l = 2m, let i ′ = m -i, j ′ = m -j , k ′ = m -k and l ′ = m -l , then for all χ ∈ Ẑ(2), we have t ∈Z(2) χ (t ) ϑ i+t ( x 1 ) ϑ j +t ( y 1 ) . t ∈Z(2) χ (t ) ϑ k+t ( u 1 ) ϑ l +t ( v 1 ) = t ∈Z(2) χ (t ) ϑ i ′ +t ( x 2 ) ϑ j ′ +t ( y 2 ) . t ∈Z(2) χ (t ) ϑ k ′ +t ( u 2 ) ϑ l ′ +t ( v 2 ) . (7) Proof: If x = y = u = v = 0 A ,
the preceding result gives the algebraic Riemann relations, a proof of which can be found in [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 333]. We just need to adapt the proof of Mumford for the general case.

Let p 1 and p 2 be the first and second projections from

A k ×A k to A k . Let = p 1 * ( )⊗ p 2 * ( ).
The theta structure Θ A k induces a theta structure Θ A k ×A k such that for (i, j ) ∈ Z(ℓn) × Z(ℓn) we have ϑ

Θ A×A i , j = ϑ Θ A k i ⊗ ϑ Θ A k j (see [Mum66, Lem. 1 p. 323]). Consider the isogeny ξ : A k × A k → A k × A k , (x, y) → (x + y, x -y). We have ξ * ( ) = 2 . Since Θ A k is a symmetric theta structure Θ A k ,
ξ * (ϑ i ⊗ ϑ j ) = λ u,v∈Z(2l n) u+v=i u-v= j (ϑ 2 u ⊗ ϑ 2 v ). (8)
Considering this equation on the affine cone, we can always choose our affine lifts such that taking the evaluation at these lifts yield λ = 1. In the following we assume this is the case. Using equation (8)

we compute for all i , j ∈ Z(2ℓn) which are congruent modulo Z(ℓn) and x, y ∈ A k (k):

t ∈Z(2) χ (t ) ϑ i+ j +t ( x + y) ϑ i-j +t ( x -y) = t ∈Z(2) u,v∈Z(2l n) u+v=i+ j +t u-v=i-j +t χ (t ) ϑ 2 u ( x) ϑ 2 v ( y) = t 1 ,t 2 ∈Z(2) χ (t 1 + t 2 ) ϑ 2 i +t 1 ( x) ϑ 2 j +t 2 ( y) =    t ∈Z(2) χ (t ) ϑ 2 i+t ( x)    •    t ∈Z(2) χ (t ) ϑ 2 j +t ( y)    . (9)
So we have:

t ∈Z(2) χ (t ) ϑ i+ j +t ( x + y) ϑ i -j +t ( x -y) . t ∈Z(2) χ (t ) ϑ k+l +t ( u + v) ϑ k-l +t ( u -v) = t ∈Z(2) χ (t ) ϑ 2 i+t ( x) • t ∈Z(2) χ (t ) ϑ 2 j +t ( y) • t ∈Z(2) χ (t ) ϑ 2 k+t ( u) • t ∈Z(2) χ (t ) ϑ 2 l +t ( v) = t ∈Z(2) χ (t ) ϑ i +l +t ( x + v) ϑ i-l +t ( x -v) . t ∈Z(2) χ (t ) ϑ k+ j +t ( u + y) ϑ k-j +t ( u -y) . (10) Now if we let x = x 0 + y 0 , y = x 0 -y 0 , u = u 0 + v 0 and v = u 0 -v 0 , we have x + y + u + v = 2(x 0 + u 0 ) so we can choose z = x 0 + u 0 , so that z -x = u 0 -y 0 , z -y = u 0 + y 0 , z -u = x 0 -v 0 , z -v = x 0 + v 0 .
By doing the same change of variable for i, j , k, l we see that the theorem is just a restatement of Equation (10). (see [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 334]).

From the generalized Riemann relations it is possible to derive addition relations.

Theorem 3.2 (Addition Formulas):

We suppose that 4|ℓn. Let x, y ∈ A k (k) and suppose that we are given x ∈ p -1

A k (x), y ∈ p -1 A k (y), x -y ∈ p -1 A k (x -y), then there is a unique point x + y ∈ A k (k) such that for i, j , k, l , m ∈ Z(ℓn) verifying i + j + k + l = 2m t ∈Z(2) χ (t ) ϑ i+t ( x + y) ϑ j +t ( x -y) . t ∈Z(2) χ (t ) ϑ k+t ( 0 A k ) ϑ l +t ( 0 A k ) = t ∈Z(2) χ (t ) ϑ -i ′ +t ( y) ϑ j ′ +t ( y) . t ∈Z(2) χ (t ) ϑ k ′ +t ( x) ϑ l ′ +t ( x) , ( 11
)
where i ′ , j ′ , k ′ , l ′ are defined as in Theorem 3.1. We have p A k ( x + y) = x + y.
Thus the addition law on A k extends to a pseudo addition law on A k ; we call it an addition chain and we note x + y = chain_add( x, y, xy).

Proof: We apply the Riemann relations (7) to x + y, xy, 0 A , 0 A . We have 2x = (x + y) + (xy)

+ 0 A + 0 A , -y = x -(x + y), y = x -(x -y), x = x -0 A , x = x -0 A so Theorem 3.1
shows that there exist a point x + y ∈ A k (k) satisfying the addition relations (11). (Remember that (ϑ i (-y)) i∈Z(ℓn) = (ϑ -i (y)) i∈Z(ℓn) , see Section 2.3.) It remains to show that this point is unique. For this, it is enough to prove that for all i, j , k, l , m ∈ Z(ℓn) such that i

+ j + k + l = 2m and all χ ∈ Ẑ(2) there exist k ′ , l ′ , m ′ ∈ Z(ℓn) such that i + j + k ′ + l ′ = 2m ′ and t ∈Z(2) ϑ k ′ +t ( 0 A k ) ϑ l ′ +t ( 0 A k ) ̸ = 0.
Then, by summing over the characters the first bracket of the left hand side of equation ( 11) we obtain the products ϑ i +t ( x + y) ϑ j +t ( xy) for i, j ∈ Z(ℓn), from which we can recover the coordinates of the point x + y. Now, let k 1 , l 1 ∈ Z(2ℓn) be such that k = k 1 + l 1 and l = k 1 -l 1 . Using formula (9), we get:

t ∈Z(2) χ (t ) ϑ k 1 +l 1 ( 0 A k ) ϑ k 1 -l 1 ( 0 A k ) =    t ∈Z(2) χ (t ) ϑ 2 k 1 +l ( 0 A k )    .    t ∈Z(2) χ (t ) ϑ 2 l 1 +t ( 0 A k )    (12)
Using [Mum66, p. 339 eq. (*)], we obtain that for all χ ∈ Z(2) there exists k ′ 1 ∈ k 1 + Z(ℓn) and l ′ 1 ∈ l 1 + Z(ℓn) such that:

   t ∈Z(2) χ (t ) ϑ 2 k 1 +l ( 0 A k )    .    t ∈Z(2) χ (t ) ϑ 2 l 1 +t ( 0 A k )    ̸ = 0.
This complete the proof.

In order to obtain an efficient algorithm to compute addition chain, we first we reformulate the addition formulas (see [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 334]). Let H = Z(ℓn) × Ẑ(2), and for (i, χ ) ∈ H define

u i,χ ( x) = t ∈Z(2) χ (t ) ϑ i +t ( x).
Then we have for all i, j , k, l , m ∈ H such that 2m = i

+ j + k + l u i ( x + y) u j ( x -y) u k ( 0 A k ) u l ( 0 A k ) = 1 2 2 g ξ ∈H ,2ξ =∈Z(2)×0 (m 2 + ξ 2 )(2ξ 1 ) u i -m+ξ ( y) u m-j +ξ ( y) u m-k+ξ ( x) u m-l +ξ ( x). (13) It is easy to see that ( ϑ i ( x)) i ∈Z(ℓn) , is determined by ( u i ( x)) i∈H . Algorithm 3.3 (Addition chain): Input x, y and x -y such that p A k ( x) -p A k ( y) = p A k ( x -y). Output x + y = chain_add( x, y, x -y). : For all i ∈ Z(ℓn), χ ∈ Ẑ(2) and X ∈ { x + y, x, y, 0 A k } compute u i,χ (X ) = t ∈Z(2) χ (t ) ϑ i+t (X ).
: For all i ∈ Z(ℓn), choose j , k, l ∈ Z(ℓn) such that i

+ j +k + l = 2m, u j ( x -y) ̸ = 0, u k ( 0 A k ) ̸ = 0, u l ( 0 A k ) ̸ = 0 and compute u i ( x + y) = 1 2 2g u j ( x -y) u k ( 0 A k ) u l ( 0 A k ) ξ ∈H ,2ξ =∈Z(2)×0 (m 2 + ξ 2 )(2ξ 1 ) u i-m+ξ ( y) u m-j +ξ ( y) u m-k+ξ ( x) u m-l +ξ ( x). ( 14
)
: For all i ∈ Z(ℓn), output

ϑ i ( x + y) = 1 2 g ξ ∈ Ẑ(2)
u i,χ ( x + y).

Complexity Analysis 3.4:

As u i +t ,χ = χ (t ) u i,χ we only need to consider (ℓn) g coordinates and the linear transformation between u and ϑ can be computed at the cost of (2nℓ) g additions in k. We also have u i,χ (-

x) = u -i ,χ ( x).
Using the fact that for t ∈ Z(2) the right hand terms of ( 14) corresponding to ξ = (ξ 1 + t , ξ 2 ) and to ξ = (ξ 1 , ξ 2 ) are the same up to a sign, one can compute the left hand side of ( 14) with 4 • 4 g multiplications and 4 g additions in k. In total one can compute an addition chain in 4.(4ℓn) g multiplications, (4ℓn) g additions and (ℓn) g divisions in k. We remark that in order to compute several additions using the same point, there is no need to convert back to the ϑ at each step so we only need to perform Step 2.

The addition chain formula is a basic step for all the algorithms to be presented in the sequel of this paper and we will use it as an unit of time for all our running time analysis. In some cases it is possible to greatly speed up this computation. See for instance [START_REF] Gaudry | Fast genus 2 arithmetic based on Theta functions[END_REF] which uses the duplication formula between theta functions to speed up the addition chain of level two. See also Section 4.1 where it is explained how to use isogenies to compute the addition chain for a general level by using only addition chains of level two, so that we can use the speed up of [START_REF] Gaudry | Fast genus 2 arithmetic based on Theta functions[END_REF] in general whatever the level of the theta structure is.

Remark 3.5:

The addition formulas can also be used to compute the usual addition law in A k by choosing j = 0 in Equation ( 14) for every i.

The addition chain law on A k induces a multiplication by a scalar law which reduces via p A k to the multiplication by a scalar deduced from the group law of A k . Let x, y ∈ A k and x + y ∈ p -1 A k (x + y), then we can compute 2x + y := chain_add( x + y, x, y). More generally there is a recursive algorithm to compute for every m 2:

m x + y := chain_add( (m -1)x + y, x, (m -2)x + y)
We put chain_multadd(n, x + y, x, y) := m x + y and define chain_mult(m, x) := chain_multadd(m, x, x, 0 A k ).

We have p A k (chain_mult(m, x)) = m. p A k ( x). We call chain_multadd a multiplication chain.

x 2m ′ := chain_add(x m ′ , x m ′ , x 0 ) x 2m ′ +1 := chain_add(x m ′ +1 , x m ′ , x 1 )
xy 2m ′ := chain_add(xy m ′ , x m ′ , xy 0 ) m ′ := 2m ′ .
Else compute

x 2m ′ +1 := chain_add(x m ′ +1 , x m ′ , x 1 ) x 2m ′ +2 := chain_add(x m ′ +1 , x m ′ +1 , x 0 ) xy 2m ′ +1 := chain_add(xy m ′ , x m ′ , xy -1 ) m ′ := 2m ′ + 1.
: Output xy m .

Correction and Complexity Analysis 3.7: It is not completely trivial to see that mx + y does not depend on the Lucas sequence used to compute it. We prove this in Corollary 3.13 where we show that multiplication chains are associative. In order to do as few division as possible, we use a Montgomery ladder [CFA + 06, Alg. 9.5] for our Lucas sequence, hence the algorithm. We see that a multiplication chain requires O(log(m)) addition chains.

.. The case n = 2

Let 0 be a principal polarization associated to a symmetric irreductible divisor Θ. Then = 2 0 is of degree 2 and we have for all i ∈ Z(2), (-1) * ϑ i = ϑ i , where (-1) is the inverse automorphism on A k . As a consequence, gives an embedding of the Kummer variety K A = A k / ± 1. Suppose that the even theta nulls for Θ are non zero. Then the embedding given by in the projective space is an immersion. (See [Kem88, Cor. 5] and [Kem92, Th. 1] or [START_REF] Koizumi | Theta relations and projective normality of abelian varieties[END_REF]Cor. 4

.5.2].)

There is no properly defined addition law on K A : from ±x ∈ K A and ±y ∈ K A , we may compute ±x ± y which gives two points on K A . However, if we are also given ±(x -y) ∈ K A , then we can identify ±(x + y) ∈ {±x ± y}. Thus the addition chain law from Theorem 3.2 extends to a pseudo addition on the Kummer variety. With our hypothesis, by looking at the proof of Theorem 11 we see that we can use it to compute the pseudo addition law on the Kummer variety.

Let x, y ∈ K A . To compute ±x ±y without ±(x -y) we can proceed as follows: let X = (X i ) i∈Z(2) , Y = (Y i ) i ∈Z(2) be the two projections of the generic point on K A × K A . Then the addition relations X = chain_add(x, y, Y ) describe a system of degree 2 in K A × K A , whose solutions are (±(x + y), ±(x -y)) and (±(xy), ±(x + y)). From this system, it is easy to recover the points {±(x + y), ±(x -y)}, but this involves a square root in k. (The preceding claims are proved in the preprint [LR10, Lemma 3].) We call this a normal addition, coming back to isogenies computations, it means that when working with n = 2, we have to avoid computing normal additions, since they require a square root and are much slower than addition chains.

Finally, to make our algorithms work with n = 2, we have to introduce the notion of compatible additions. Suppose that we are given ±x, ±y, ±z ∈ K A , together with ±(x + y), and ±(y + z). Using a normal addition we can compute {±(x + z), ±(x -z)}; we want to find ±(x + z). If we apply the normal addition to ±x + y and ±x + z we find {±(2x + y + z), ±(y -z)} while the normal addition applied to ±x + y and ±x -z give {±(2x + yz), ±(y + z)}. This allows us to identify ±(x + z) if we suppose 2x ̸ = 0, 2y ̸ = 0, 2z ̸ = 0, and 2(x + y + z) ̸ = 0. We call this the compatible addition ±(x + z) with ±(x + y) and ±(y + z).

. Theta group and addition relations

In this Section, we study the action of the theta group on the addition relations. We also show that addition relations are compatible with isogenies between two abelian varieties with compatible theta structures. By combining this we find the addition relations linking the coordinates of the points

{ R i } i ∈Z(ℓn) on B k . By considering different modular point (a i ) i∈Z(ℓn) ∈ ϕ -1 1 ((b i ) i∈Z(n)
) and the associated isogenies π : A k → B k , we can then understand the addition chains between any isotropic subgroup of B k [ℓ] (see Section 1). In particular we exploit this to show that we can compute the chain multiplication by ℓ in O(log(ℓ)) addition chains.

Given the way the addition relations are set up as a consequence of the isogeny theorem, there should be no surprise that they are compatible with the action of the theta group. Still, some care must be taken, if we have x, y, x + y and xy ∈ A k (k) such that

x + y = chain_add( x, y, xy), and we take g 1 , g 2 ∈ G( ), then by looking at the projections in A k we certainly have

(g 1 • g 2 ). x + y = λ chain_add(g 1 . x, g 2 . y, (g 1 • g -1 2 ). x -y)
where λ ∈ k × . However for trivial reasons, λ ̸ = 1 in general (See Lemma 3.10), so we have to work a bit to determine λ. We begin with two easy lemmas.

Lemma 3.8:

Suppose that x 1 , y 1 , u 1 , v 1 , x 2 , y 2 , u 2 , v 2 ∈ A k (k)
satisfy the general Riemann relations (7).

• For every g ∈ G( ), g . x 1 , g . y 1 , g . u 1 , g . v 1 , g . x 2 , g . y 2 , g . u 2 , g . v 2 also satisfy the Riemann relations.

• For every ℓ-isogeny of type 1 π :

(A, , Θ A k ) → (B, 0 , Θ B k ) such that Θ B k is π-compatible with Θ A k , then π( x 1 ), π( y 1 ), π( u 1 ), π( v 1 ), π( x 2 ), π( y 2 ), π( u 2 ), π( v 2 ) ∈ B k also satisfy the Riemann relations.
Proof: This is an immediate computation.

Lemma 3.9: Let (α, i, j ) ∈ (ℓn) and x ∈ A k . Then we have -(α, i , j ). x = (α, -i, -j ).(x), and π(x) = -π( x).

In particular -(α, i, j ). 0 A k = (α, -i, -j ). 0 A k .

Proof: If x = (x i ) i ∈Z(ℓn) ,we recall that we have defined -x = (x -i ) i ∈Z(ℓn) . The fact than -(α, i , j ). x = (α, -i, -j ).(x) is a direct consequence of the fact than the coordinates ( ϑ i ) i∈Z(ℓn) of x are the theta functions associated to a symmetric theta structure. We can also check this with a direct computation: If u ∈ Z(ℓn) we have by (1): ((α, i , j ). x) u = α〈-ui , j 〉a u+i , ((α, -i, -j ). x) -u = α〈u + i, -j 〉 x -u-i = a u+i = x u . The rest of the lemma is trivial.

We now turn to the action of (ℓn) on A k . Since (ℓn) is generated by k * , Z(ℓn) and Ẑ(ℓn) (where we embed Z(ℓn) and Ẑ(ℓn) in (ℓn) with the usual sections), it is enough to study separately the action of these subgroup on the addition relation. The action of k * is immediate: Lemma 3.10: For λ x , λ y , λ x-y ∈ k * and x, y ∈ A k (k), we have:

chain_add(λ x x, λ y y, λ x-y x -y) = λ 2 x λ 2 y λ x-y chain_add( x, y, x -y), (15) chain_multadd
Proof: Formula (15) is an immediate consequence of the addition formulas (11). The rest of the lemma follows by an easy recursion.

A more interesting result is the compatibility between the addition formulas and the action of Z(ℓn) on A k : Proposition 3.11 (Compatibility of the pseudo-addition law): For x, y, xy ∈ A k (k), and i , j ∈ Z(ℓn), we have:

(1, i + j , 0). chain_add( x, y, xy) = chain_add((1, i , 0). x, (1, j , 0). y, (1, ij , 0). xy) (18)

In particular if we set P i = (1, i, 0). 0 A k we have: P i + j = chain_add( P i , P j , P i-j ) Proof: Let x + y = chain_add( x, y, xy). By Theorem 3.2, we have for every a, b , c, d , e ∈ Z(ℓn) such that a + b + c + d = 2e:

t ∈Z(2) χ (t )ϑ a+t ( x + y)ϑ b +t ( x -y) . t ∈Z(2) χ (t )ϑ c+t ( 0)ϑ d +t ( 0) = t ∈Z(2) χ (t )ϑ -e+a+t ( y)ϑ e-b +t ( y) . t ∈Z(2) χ (t )ϑ e-c+t ( x)ϑ e-d +t ( x) . (19) Applying (19) to a ′ = a + i + j , b ′ = b + i -j , c ′ = c, d ′ = d , e ′ = e + i, it comes: t ∈Z(2) χ (t )ϑ i+ j +a+t ( x + y)ϑ b +i-j +t ( x -y) . t ∈Z(2) χ (t )ϑ c+t ( 0)ϑ d +t ( 0) = t ∈Z(2) χ (t )ϑ -j -e+a+t ( y)ϑ j +e-b ( y) . t ∈Z(2) χ (t )ϑ i +e-c+t ( x)ϑ i +e-d +t ( x) . (20)
Thus (1, i + j , 0). x + y, (1, i, 0). x, (1, j , 0). y and (1, ij , 0). xy satisfy the additions relations.

By applying π, we obtain the following corollary: Corollary 3.12: For x, y, xy ∈ A k , and i, j ∈ Z(ℓn), we have:

π i + j (chain_add( x, y, x -y)) = chain_add( π i ( x), π j ( y), π i -j ( x -y)).
Proof: Remember that by definition π i ( x) = π((1, i , 0). x). The lemma is then a trivial consequence of Proposition 3.11 and Lemma 3.8. We remark that by setting x = y = 0 A k in Corollary 3.12, we find

R i+ j = chain_add( R i , R j , R i -j ).
By considering different isogenies π : A k → B k , we can use Corollary 3.12 to study the associativity of chain additions: Corollary 3.13: Let x ∈ B k [ℓ] and y ∈ B k . Choose any affine lifts x, y and x + y of respectively x, y and x + y.

1. For all n ∈ * ,we put n x = chain_mult(n, x) and n x + y = chain_multadd(n, x + y, x, y).

Then for all n 1 , n 2 ∈ * such that n 1 > n 2 , we have

(n 1 + n 2 )x = chain_add( n 1 x, n 2 x, (n 1 -n 2 )x), (21)
(n 1 + n 2 )x + y = chain_add( n 1 x + y, n 2 x, (n 1 -n 2 )x + y). (22)
In particular, we see that n x + y and n x do not depend on the particular sequence of chain_add used to compute them.

2. For all n ∈ * , -n x + y = chain_add(n, -( x + y), -x, -y)

Proof: First we prove assertion 1. Let K be a subgroup of B k [ℓ] containing x which is maximal and isotropic for the Weil pairing. Consider the isogeny π : B k → D k = B k / K and let π : D k → B k be the contragredient isogeny. We choose any theta structure on (D k , π * 0 ) compatible with π. There exist i, j ∈ Z(ℓ) and λ i , λ j ∈ k * such that x = λ i π i ( 0 D k ) and y = λ j π j ( 0 D k ). If λ i = λ j = 1, then the assertion 1. of Corollary 3.13 is a consequence of Corollary 3.12. But it is easy (see Lemma 3.10) to see that (21) is homogeneous in λ i , hence the result.

Next we prove assertion 2. Once again, let i ∈ Z(ℓ) be such that x = λ i π (1, i , 0). 0 D k , and let y ′ be any point in π -1 ( y). By homogeneity we may suppose that λ i = 1. By Corollary 3.12 and Proposition 3.11, we have n x + y = π (1, n.i, 0). y ′ . Now by Lemma 3.9, we have -

n x + y = π -(1, n.i, 0). y ′ = π (1, -n.i, 0). -y ′ = chain_add(n, -( x + y), -x, -y).
The following remark concerning Corollary 3.12 is a useful fact to study the case ℓ not prime to n: Remark 3.14: Let x ∈ A k , i ∈ Z(ℓn) and let y = π( x). Let m ∈ be such that ℓ|m. By Proposition 3.11 and Corollary 3.12, we have π ((1, mi, 0). x) = chain_multadd(m, π i ( x), R i , y).

But if ℓ|m, then mi ∈ Z(n) ⊂ Z(ℓn). By Proposition 2.3 we have π ((1, mi, 0). x) = (1, mi, 0). y, and (1, mi , 0). y can be computed with the formulas (1). Hence

(1, mi, 0). y = chain_multadd(m, π i ( x), R i , y).

♦

In order to have a complete picture of the action of (ℓn) on A k , we have yet to describe the action of Ẑ(ℓn) on A k . In order to do so, we recall from Section 2.2 that I is the automorphism of the Theta group that permutes K 1 and K 2 . Since s K 2 ( ) = I • s K 1 ( ) • I, we just have to explain what is the action of of I on the addition relations.

Proposition 3.15: Suppose that x, y, u, v, x ′ , y ′ , u ′ , v ′ ∈ A k (k) satisfy the general Riemann equations (7). Then I.x, I.y, I.u, I.v, I.x ′ , I.y ′ , I.u ′ , I.v ′ also satisfy (7).

Proof: If x = (x i ) i ∈Z(ℓn) we recall (see ( 5)) that

I.x = ( j ∈Z(ℓn) e(i , j )x j ) i ∈Z(ℓn)
where e = e is the commutator pairing.

By hypothesis, we have for i, j , k, l ∈ Z(ℓn) such that i

+ j + k + l = 2m: t ∈Z(2) ϑ i +t (x) ϑ j +t (y) . t ∈Z(2) ϑ k+t (u) ϑ l +t (v) = t ∈Z(2) ϑ i ′ +t (x ′ ) ϑ j ′ +t (y ′ ) . t ∈Z(2) ϑ k ′ +t (u ′ ) ϑ l ′ +t (v ′ ) . (23) Let A χ ,x,y,i , j = t ∈Z(2) χ (t ) ϑ i +t (x) ϑ j +t (y) . If I , J , K, L ∈ Z(ℓn) are such that I + J + K + L = 2M , we have: A χ ,I.x,I.y,I ,J = T ∈Z(2) χ (T ) i ∈Z(ℓn) e(I + T , i) ϑ i (x) j ∈Z(ℓn) e(J + T , j ) ϑ j (x) = T ∈Z(2),i , j ∈Z(ℓn) χ (T )e(T , i + j )e(I , i)e(J , j ) ϑ i (x) ϑ j (y)
A χ ,I.x,I.y,I ,J A χ ,I.u,I.v,K,L = T 1 ,T 2 ∈Z(2) i , j ,k,l ∈Z(ℓn) χ (T 1 + T 2 )e(T 1 , i + j )e(T 2 , k + l )e(I , i)e(J , j )e(K, k)e(L, l e(I , i + t 1 )e(J , j + t 1 )e(K, k + t 2 )e(L, l + t 2 ) ϑ i+t 1 (x) ϑ j +t 1 (y) ϑ k+t 2 (u) ϑ l +t 2 (v) = λe(I , i)e(J , j )e(K, k)e(L, l )

) ϑ i (x) ϑ j (y) ϑ k (u) ϑ l (v) = i, j ,k,l ∈Z(ℓn) e(I , i)e(J , j )e(K, k)e(L, l ) ϑ i (x) ϑ j (y) ϑ k (u) ϑ l (v) T 1 ,T 2 ∈Z(2) χ (T 1 + T 2 )e(T 1 , i + j )e(T 2 , k + l ) But T 1 ,T 2 ∈Z(2) χ (T 1 + T 2 )e(T 1 , i + j )e(T 2 , k + l ) = 4 g if e(•, i + j ) = e(•, k + l ) = χ
t 1 ,t 2 ∈Z(2) ϑ i+t 1 (x) ϑ j +t 1 (y) ϑ k+t 2 (u) ϑ l +t 2 (v) =
λe(I , i)e(J , j )e(K, k)e(L, l )

t 1 ,t 2 ∈Z(2) ϑ i ′ +t 1 (x ′ ) ϑ j ′ +t 1 (y ′ ) ϑ k ′ +t 2 (u ′ ) ϑ l ′ +t 2 (v) = λe(I ′ , i ′ )e(J ′ , j ′ )e(K ′ , k ′ )e(L ′ , l ′ ) t 1 ,t 2 ∈Z(2) ϑ i ′ +t 1 (x ′ ) ϑ j ′ +t 1 (y ′ ) ϑ k ′ +t 2 (u ′ ) ϑ l ′ +t 2 (v)
where λ = 4 g if i + j + k + l = 2m and λ = 0 otherwise. By combining these relations we find that A χ ,I.x,I.y,I ,J A χ ,I.u,I.v,K,L = A χ ,I.x ′ ,I.y ′ ,I ′ ,J ′ A χ ,I.u ′ ,I.v ′ ,K,L .

which concludes the proof.

Corollary 3.16: Let x, y, xy ∈ A k (k), and let i, j ∈ Z(ℓn), k, l ∈ Ẑ(ℓn). Then we have:

(1, i + j , k + l ). chain_add( x, y, x -y) = chain_add((1, i, k). x, (1, j , l ). y, (1, i -j , k -l ). x -y). ( 24
)
Proof: By Propositions 3.11 and 3.15 we have (1, 0, k + l ). chain_add( x, y, xy) = chain_add((1, 0, k). x, (1, 0, l ). y, (1, 0, kl ). xy) (25) Now since (1, i, k) = (1, 0, k)(1, i , 0), we conclude by combining Equations ( 18) and (25).

Using Proposition 3.15, we can prove that the addition relations are compatible with any isogeny.

Corollary 3.17:

Suppose that x 1 , y 1 , u 1 , v 1 , x 2 , y 2 , u 2 , v 2 ∈ A k satisfy the Riemann relations (7). If π : (A, , Θ A k ) → (B, 0 , Θ B k ) is an isogeny such that Θ B k is π-compatible with Θ A k , then π( x 1 ), π( y 1 ), π( u 1 ), π( v 1 ), π( x 2 ), π( y 2 ), π( u 2 ), π( v 2 ) ∈ B k
also satisfy the general Riemann Relations. In particular, for all x, y, xy ∈ A k , we have

π(chain_add( x, y, x -y) = chain_add( π( x), π( y), π( x -y)).
Proof: It is easy to see that Lemma 3.8 is valid for any compatible isogenies of type 1 (it is not restricted to ℓ-isogenies). By Proposition 3.15, we can apply Lemma 3.8 also in the case of compatible isogenies of type 2, which concludes since every compatible isogeny is a composition of isogenies of type 1 or 2.

 Application of the addition relations to isogenies

In this Section we apply the results of Section 3 to the computation of isogenies (see Section 4.2). More precisely, we present an algorithm to compute the isogeny π : B k → A k from the knowledge of the modular point 0 A k . We give in Section 5 algorithms to compute 0 A k from the kernel of π.

But first, we remark that since the embedding of A k that we consider is given by a theta structure of level ℓn, a point π(x) is given by (ℓn) g coordinates, which get impractical because of memory consumption when ℓ is big. In order to mitigate this problem, in Section 4.1, we give a point compression algorithm such that the number of coordinates of a compressed point does not depend on ℓ.

We recall that we have chosen in Section 3.1

0 A k = (a i ) i∈Z(ℓn) such that π( 0 A k ) = 0 B k , and that we have defined for i ∈ Z(ℓn), R i = (a i + j ) j ∈Z(n) ∈ B k (k).

. Point compression

Suppose that ℓ is prime to n. We know that x ∈ A k (k) can be recovered from ( π i ( x)) i ∈Z(ℓ) , by

( x) ni+ℓ j = ( π i ( x)) j . If (d 1 , • • • , d g
) is a basis of Z(ℓ), we can prove that x can be easily computed from just (

π d i ( x)) i ∈[1..g ] and ( π d i +d j ( x)) i, j ∈[1..g ] ). If (e 1 , • • • , e g )
is the canonical basis of Z(ℓn), in the following, we take

(d i = ne i ) i ∈[1.
.g ] as a basis of Z(ℓ).

Proposition 4.1: Let x ∈ A k (k) and i, j ∈ Z(ℓn). We have

π i + j ( x) = chain_add( π i ( x), R j , π i -j ( x)).
Proof: We apply Corollary 3.12 with y = 0 A k , xy = x, so that we have chain_add( x, y, xy) = x. We obtain:

π i+ j ( x) = chain_add( π i ( x), π j ( 0 A k ), π i-j ( x)).

Definition 4.2:

Let S ⊂ G be a subset of a finite abelian group G such that 0 G ∈ S. We denote by S ′ the smallest subset of G (for the inclusion) such that S ′ ⊃ S and

S ′ = S ′ {x + y|x ∈ S ′ , y ∈ S ′ , x -y ∈ S ′ }. We say that S is a chain basis of G if S ′ = G. Example 4.3: Let G = Z(ℓ). Let (e 1 , • • • , e g ) be the canonical basis of G. If ℓ is odd, a chain basis of G is given by S = {0 G , e i , e i + e j } i , j ∈[1.. g ],i < j .
If ℓ is even, a chain basis of G is given by

S = {0 G , e i 1 , e i 1 + e i 2 , • • • , e i 1 + • • • + e i g } i 1 ,••• ,i g ∈[1..g ],i 1 <•••<i g .
In each case, the chain basis S is minimal, we call it the canonical chain basis S(G) of G.

We recall that, in Example 2.5, we have defined ⊂ Z(ℓn) such that + Z(n) = Z(ℓn). To we associate a canonical chain basis S ⊂ as follow: if ℓ is prime to n, then = Z(ℓ) ⊂ Z(ℓn), and we define S = S(Z(ℓ)

) = {d 1 , • • • , d g , d 1 +d g , • • • , d g -1 +d g }.
Otherwise we take S = S(Z(ℓn)).

Theorem 4.4 (Point compression):

Let x ∈ A k (k). The point x is uniquely determined by 0 A k and { π i ( x)} i ∈S . Moreover, 0 A k is uniquely determined by { π i ( 0 A k )} i∈S = { R i } i ∈S .
Proof: By Proposition 3.11 we have

π i + j ( x) = chain_add( π i ( x), π j ( 0 A k ), π i -j ( x), 0 B k ). So by induction, from { π i (x)} i ∈S we can compute every { π i (x)} i∈S ′ . Since S ′ = (or contains if n is not prime to ℓ), Corollary 2.4 shows that x is entirely determined by { π i (x)} i ∈S and { π i ( 0 A k )} i ∈S . In particular, 0 A k is entirely determined by { π i ( 0 A k )} i ∈S . But π i ( 0 A k ) = π( P i
) by Proposition 2.3 and we are done.

In the description of the algorithms, we suppose that ℓ is prime to n, so that = Z(ℓ) ⊂ Z(ℓn).

Algorithm 4.5 (Point compression):

Input x = ( ϑ i ( x)) i∈Z(ℓn) ∈ A k (k) Output The compressed coordinates ( π i ( x)) i∈S . : For each i ∈ S, output ( π i ( x)) = ( ϑ ni+ℓ j ( x)) j ∈Z(n) Algorithm 4.6 (Point decompression): Input The compressed coordinates π( x) i∈S of x. Ouput x = ( ϑ i ( x)) i∈Z(ℓn) ∈ A k (k). : (Step 1) Set ′ := S. : (Step 2) While ′ ̸ = . • Choose i , j ∈ ′ such that i + j ∈ \ ′ and i -j ∈ ′ . • Compute π i+ j ( x) = chain_add( π i ( x), R j , π i-j ( x)). • ′ := ′ {i + j }. : (Step 3) For all i ∈ Z(ℓn), write i = ni 0 + ℓ j and output ϑ i (x) = π i 0 ( x) j .
Correction and Complexity Analysis 4.7: By using repeatedly the formula from Proposition 3.11:

π i+ j ( x) = chain_add( π i ( x), R j , π i-j ( x), 0 B k ) we can reconstitute every π i ( x) for i ∈ Z(ℓ) in
Step 2 since S is a chain basis of Z(ℓ). We can then trivially recover the coordinates of x in Step 3 since they are just a permutation of the coordinates of the { π i ( x), i ∈ Z(ℓ)} (see Section 2.4). To recover x, we need to do # -#S = O(ℓ g ) chain additions. The compressed point { π i ( x)} i∈S is given by #S × n g coordinates.

If ℓn = 2n 0 and n 0 is odd we see that we can store a point in A k with 2 g (1 + g (g + 1)/2) coordinates (4 g if n 0 is even) rather than (2n 0 ) g .

.. Addition chains with compressed coordinates

Let x, y and xy ∈ A k . Suppose that we have the compressed coordinates ( π i ( x)) i∈S , ( π i ( y)) i ∈S , ( π i ( xy)) i ∈S . Then if i ∈ S we have by Corollary 3.12

π i ( x + y) = chain_add( π i ( x), π 0 ( y), π i ( x -y),
hence we may recover the compressed coordinates of x + y.

We can compare the running time of addition chain with the full coordinates representation (of level ℓn) and the compressed representation. By the formulas from Theorem 3.2, since 2|n and the formulas sum over points of 2-torsion, we see that we are doing # addition chains in B k using representations of level n. The additions chains with the compressed representation are much faster than the addition chains with the full representation since we need to do only #S addition chains of level n. In particular, since we can compute the multiplication by m with chain additions, we see that the cost of a multiplication by m is O(#S log(m)) addition chains of level n (and a point decompression if we want to recover the full coordinates).

Since we can take n = 2, the additions formulas of level 2 allows us to compute addition chains of any level. In particular the speed up for these formulas given by [START_REF] Gaudry | Fast genus 2 arithmetic based on Theta functions[END_REF] can be used for all levels.

. Computing the dual isogeny

We recall that we have the following diagram:

y ∈ B k (k) z ∈ A k (k) x ∈ A k (k) π π [ℓ] Let y ∈ p -1 B k (y) and let x ∈ A k (k) be such that π( x) = y. Let i ∈ Z(ℓ).
In this section, we describe an algorithm to compute π i (ℓ. x) efficiently from the knowledge of y and 0 A k (i.e. without using x which may be hard to compute). By using this algorithm for

i ∈ {d 1 , • • • , d g , d 1 + d 2 , • • • d g -1 + d g },
we can then recover π(y) = p A k (ℓ. x) (see Theorem 4.4), where (d i ) i ∈[1..g ] is the basis of Z(ℓ) defined in Section 4.1). We know that π i (x) = y + R i where x = p A k ( x). For i ∈ Z(ℓ), we choose a point

π a i (x) ∈ p -1 A (y + R i ) so that for each i ∈ Z(ℓ) there exists λ i ∈ k * such that π i ( x) = λ i π a i (x). If x ′ is another point in π -1 ( y), then we have π i ( x ′ ) = λ ′ i π a i (x), with λ ′ i = ζ λ i , ζ a ℓ t h -root
of unity by Section 2.3. As a consequence, it is possible to recover λ i only up to an ℓ t h -root of unity, but this information is sufficient to compute π i (ℓ. x):

The kernel of the isogeny We know that the kernel of the isogeny π :

B k → A k is the subgroup K generated by {R d i } i ∈[1..g ] . For y ∈ B k [ℓ], let y ∈ p -1 B k (y).
Up to a projective factor, we may suppose that chain_mult(ℓ, y) = 0 B k . Then y is in K if and only if for all i ∈ Z(ℓ) we have π i ( π( y)) = R i . Let y + R i be any affine point above y + R i . Since y and R i are points of ℓ-torsion, for all i ∈ Z(ℓ), there exist α i ,

β i ∈ k * such that chain_multadd(ℓ, y + R i , y, R i )) = α i R i and chain_multadd(ℓ, y + R i , R i , y) = β i y. By Theorem 4.8, we know that π i ( π( y)) = α i β i R i . In particular y ∈ K if and only if α i β i
= 1 for all i ∈ Z(ℓn). In fact, we will show in Section 6 that

α i /β i = e ℓ 0 (y, R i ) where e ℓ 0
is the commutator pairing on ℓ 0 . This is coherent with the fact that

y is in K if and only if e ℓ 0 (y, R i ) = 1 for i ∈ {d 1 , • • • , d g }.
The case (n, ℓ) > 1 In this case we have to take

S = {e 1 , • • • , e g , e 1 + e 2 , • • • }. If i ∈ S, R i
is a point of ℓn-torsion and we have by Remark 3.14

(1, ℓi , 0). y = λ ℓ i chain_multadd(ℓ, π a i (x), R i , y),
so that we can still recover λ ℓ i .

The case n = 2 The only difficult part here is the ordinary additions y + R i , since the addition chains do not pose any problems with n = 2. In particular, we first choose one of the two points ±(x ± R e 1 ), which requires a square root. Now, since we have 0 A k given by a theta structure of degree ℓn > 2, we have the coordinates of R e 1 + R i on B k . This means that we can compute the compatible additions x + R i from x + R e 1 and R e 1 + R i .

 The computation of a modular point

We recall that (A k , , Θ A k ) and (B k , 0 , Θ B k ) are marked abelian varieties and we let π : A k → B k be an isogeny of type 1. In Section 5.1, we explain how to compute the theta null point 0 A k from the knowledge of the kernel of π the contragredient isogeny of π. This section introduces the notion of an excellent point of ℓ-torsion, which is an affine lift of a point of ℓ-torsion that satisfy Equation (29). We study this notion in Section 5.2, and use it in Section 5.3 in order to compute all (or just one) modular points.

. An analog of Vélu's formulas

We have seen in Section 4.2 how to use the addition formula to compute the isogeny π :

B k → A k . The theta null point (a i ) i ∈Z(ℓn) corresponding to (A k , , Θ A k
) is an input of this computation. In this section, we explain how to recover the theta null point (a i ) i ∈Z(ℓn) , given the kernel K = {T i } i ∈Z(ℓ) of π, by using only the addition relations. By combining this result with the algorithm of Section 4.2, we obtain an analog of Vélu's formulas for higher dimensional abelian varieties since we are able to compute an isogeny from the data of its kernel just by using addition relations. As in the course of the algorithm we have to take ℓ t h -root in k, we suppose that k is algebraically closed. (If k = q , with ℓ|q -1 so that the ℓ t h -root of unity are in k, we only have to work over an extension of degree ℓ of k).

Let {T d 1 , • • • , T d g } be a basis of K. Let (a i ) i ∈Z(ℓn) be the theta null point corresponding to any theta structure on A k π-compatible with the theta structure of (B k , 0 , Θ B k ). We recall that to 0 A k = (a i ) i ∈Z(ℓn) , one can associate the points ( R i ) i∈Z(ℓ) = π i ( 0 A k ) and Corollary 2.4 shows that this correspondence is one on one. By [FLR09, Prop. 7], we recover all the theta null points of the π-compatible theta structures on A k , by acting over

0 A k = ( R i ) i∈Z(ℓ) by ( R i ) i∈Z(ℓ) → ( R ψ 1 (i) ) i∈Z(ℓ) , (26)
( R i ) i ∈Z(ℓ) → (e(ψ 2 (i), i ) R i ) i∈Z(ℓ) , (27)
where ψ 1 is an automorphism of Z(ℓ) and ψ 2 is a symmetric endomorphism of Z(ℓ). We remark that the results of Section 4.1 show that

0 A k is completely determined by { R d i , R d i +d j } i, j ∈[1..g ] where d 1 , • • • , d g is a basis of Z(ℓ).
Up to an action (26) we may suppose that 0 A k is such that

π d i ( 0 A k ) = T d i . Let i ∈ Z(ℓ)
and let T i be any affine point above T i , we have

R i = λ i T i . Write ℓ = 2ℓ ′ + 1, since R i = p B k ( R i ) is a point of ℓ-torsion, we have (1, ℓ ′ + 1, 0). R i = -(1, ℓ ′ , 0). R i .
By Proposition 3.11 and Lemma 3.10, we have

chain_mult(ℓ ′ + 1, R i ) = -chain_mult(ℓ ′ , R i ), λ (ℓ ′ +1) 2 i chain_mult(ℓ ′ + 1, T i ) = -λ ℓ ′2 i chain_mult(ℓ ′ , T i ), λ ℓ i chain_mult(ℓ ′ + 1, T i ) = -chain_mult(ℓ ′ , T i ). (28)
Hence we may find λ i up to an ℓ t h -root of unity. If we apply this method for i ∈ {d 1 ,

• • • , d g , d 1 + d 2 , • • • , d g -1 + d g }
, we find R i up to an ℓ t h -root of unity. But the action (27) shows that every such choice of R i gives a valid theta null point 0 A k via the correspondence of Corollary 2.4.

Algorithm 5.1 (Vélu's like formula):

Input T d 1 , • • • T d g a basis of the kernel K of π.
Output The compressed coordinates of 0 A k , the theta null point of level ℓn corresponding to π.

Let S = {d 1 , • • • , d g , d 1 + d 2 , • • • d g -1 + d g }.
: Let ℓ ′ such that ℓ = 2ℓ ′ + 1. : For i, j ∈ [1..g ], compute the points T d i + T d j .

: For each i ∈ S,

• Choose any affine lift T ′ i of T i , and compute (β i j ) j ∈Z(n) := chain_mult(ℓ ′ , T ′ i ), and

(γ i j ) j ∈Z(n) := chain_mult(ℓ ′ + 1, T ′ i ). • Compute α i such that (γ i j ) j ∈Z(n) = α i (β i -j ) j ∈Z(n) . • Output R i := (α i ) 1 ℓ • T ′ i .
Correction and Complexity Analysis 5.2:

In the Output we compute R i ,one of the ℓ affine lift of T i such that: chain_mult(ℓ ′ +1, R i ) = -chain_mult(ℓ ′ , R i ).

Then { R i } i∈S give the compressed coordinates of 0 A k , we can then recover 0 A k by doing a point decompression (see Algorithm 4.7).

To find R i , we need to do two chain multiplications of length ℓ/2, and then take an ℓ t h -root of unity. After g (g + 1)/2 such operations, we obtain the compressed coordinates of a 0 A k , and we may recover the full coordinates of the corresponding 0 A k using the point decompression algorithm 4.7. We remark that we only need the compressed coordinates of 0 A k to compute the compressed coordinates of π. In total we need to compute g (g + 1)/2 ℓ t h -roots of unity and O( 1 2 g (g + 1) log(ℓ)) additions in B k to recover the compressed coordinates of 0 A k . We can then recover the full coordinates of 0 A k at the cost of O(ℓ g ) additions in B k .

The case (n, ℓ) > 1. In this case once again we have to recover R i for i ∈ S = {e 1 , • • • , e g , e 1 + e 2 , • • • , e 1 +e g }. Suppose that we have {T i } i ∈Z(ℓ) ,ℓ g points of ℓn-torsion such that ℓ.T i = (1, ℓi , 0).0 B .

If i ∈ S, we may suppose that R i = λ i T i .

If ℓ = 2ℓ ′ + 1 is odd, we have:

λ ℓ i chain_mult(ℓ ′ + 1, T i ) = -(1, ℓ(n -1), 0). chain_mult(ℓ ′ , T i )
so that once again we can find λ ℓ i . The kernel of π is then K = {nT i } i ∈Z(ℓ) . Even if K is isotropic, it may be {T i } i ∈Z(ℓ) are not isotropic, so some care must be taken when we choose the {T i } i ∈Z(ℓ) .

If ℓ = 2ℓ ′ is even, we have:

λ 2ℓ i chain_mult(ℓ ′ + 1, T i ) = -(1, ℓ(n -1), 0). chain_mult(ℓ ′ -1, T i ),
so that we can recover only λ 2ℓ i . But every choice still corresponds to a valid theta null point (a i ) i ∈Z(ℓn) , because when 2|ℓ, to the actions (26) and ( 27) we have to add the action given by the change of the maximal symmetric level structure [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF]Prop. 7].

The case n = 2 Once again, the only difficulty rests in the standard additions. Using standard additions, we may compute R e 1 ±R e 2 , • • • , R e 1 ±R e g , making a choice each time. Then we can compute R e i + R e j by doing an addition compatible with R e 1 + R e i and R e 1 + R e j .

. Theta group and ℓ-torsion

Let x ∈ B k (k) be such that p B k (x) is a point of ℓ-torsion. We say that x is an excellent point of ℓ-torsion if x satisfy:

chain_mult(ℓ ′ + 1, x) = -chain_mult(ℓ ′ , x). ( 29
)
Remark 5.3: If x is an excellent point of ℓ-torsion, then Lemma 3.10 shows it is also the case for λ. x for any λ an ℓ t h -root of unity. ♦

We have seen in the preceding section the importance of taking lifts that are excellent points of ℓ-torsion. The aim of this section is to use the results of Section 3.3 to show that the addition chain of excellent points of ℓ-torsion is again an excellent-point of ℓ-torsion. This result will be used in Section 5.3 to compute excellent affine lifts of B k [ℓ] by taking as few ℓ t h -roots as possible.

Let 0 = [ℓ] * 0 on B k . As 0 is symmetric, we have that 0 ≃ ℓ 2 0 [Mum70, p. 59] and K( 0 ), the kernel of 0 is isomorphic to K(ℓ 2 n). Let Θ B k , 0 be a theta structure on (B k , 0 ) [ℓ]-compatible with the theta structure Θ B k on (B k , 0 ). As in Section 2.3, we can define the affine cone B k ′ associated to the canonical sections of 0 defined by the theta structure Θ B k , 0 . We choose a system of affine coordinates on B k ′ above the projective coordinates given by Θ B k , 0 , and we let [ℓ] : B k ′ → B k be the lift to the affine cone of [ℓ] compatible with these coordinates. Finally, we note

0 B k ′ ∈ B k ′ the affine lift of the theta null point associated to Θ B k , 0 such that [ℓ] 0 B k ′ = 0 B k . Since 0 ≃ ℓ 2 0 , the natural action of G( 0 ) on H 0 ( 0 ) gives via Θ B k , 0 an action of (ℓ 2 n) on H 0 ( 0 ). Lemma 5.4: Let y ∈ B k [ℓ](k), y ∈ p -1 B k (y) and x ∈ [ℓ] -1 ( y). Then there exists (α, ni, n j ) ∈ k ℓ × Z(ℓ 2 n) × Ẑ(ℓ 2 n) such that x = (α, ni , n j ). 0 B k ′ .
Moreover, y is an excellent point of ℓ-torsion if and only if α = λ i , j µ where µ is an ℓ t h -root of unity and λ

i, j = 〈i, j 〉 ℓ ′ n(ℓ-1) . (If x ′ ∈ B k ′ (k), then x ′ ∈ [ℓ] -1 (y) if and only if x ′ = (1, ℓi ′ , ℓ j ′ ).x where (i ′ , j ′ ) ∈ Z(ℓ 2 n) × Ẑ(ℓ 2 n))
, so the class of α in k * /k * ℓ does not depend on x but only on y).

Proof: Since p B k ′ ( x) ∈ B k [ℓ 2 ],
there is an element h ∈ (ℓ 2 n) such that x = h.0 B k ′ , with h = (α, ni , n j ). By Remark 5.3, we only need to check that (λ i , j , ni , n j ).0 B k ′ is an excellent point of ℓtorsion. Let m ∈ , and let x m = chain_mult(m, x), y m = chain_mult(m, y). By Corollary 24 we have x m = (λ m 2 i , j , m • i, m • j ).0 B k ′ , and by Corollary 3.17

y m = [ℓ](λ m 2 i , j , m • i, m • j ).0 B k ′ .
So by Lemma 3.9

y ℓ ′ = [ℓ](λ ℓ ′2 i, j , ℓ ′ • i , ℓ ′ • j ).0 B k ′ = [ℓ](1, ℓn(ℓ -1)i, ℓn(ℓ -1) j )(λ ℓ ′2 i , j , ℓ ′ i , ℓ ′ j +).0 B k ′ = 〈ℓ ′ i , ℓn(ℓ -1) j 〉 [ℓ](λ ℓ ′2 i, j , (ℓ ′ + ℓn(ℓ -1)) • i, (ℓ ′ + ℓn(ℓ -1)) • j ).0 B k ′ = λ ℓ i , j [ℓ](λ (ℓ ′ +1) 2 i , j /λ ℓ i , j , -(ℓ ′ + 1) • i , -(ℓ ′ + 1) • j ).0 B k ′ = [ℓ](-x ℓ ′ +1 ) = -y ℓ ′ +1 . Proposition 5.5: Let y 1 , y 2 , y 1 -y 2 ∈ B k (k) be excellent points of ℓ-torsion. Then y 1 + y 2 := chain_add( y 1 , y 2 , y 1 -y 2 ) is an excellent point of ℓ-torsion.
points are given in Mumford coordinates, but we can use the results of Wamelen [START_REF] Wamelen | Equations for the Jacobian of a hyperelliptic curve[END_REF] to have them in theta coordinates. This algorithm is in O(ℓ 6 ) (where we use the notation O to mean we forget about the log factors). The computation of the excellent affine points of ℓ-torsion from Algorithm 5.6 is in O(ℓ 4 ), and each of the O(ℓ 3 ) isogeny requires O(ℓ 2 ) multiplication by an ℓ t h -root of unity. In total we see that we can compute all (ℓ, ℓ)-isogenies in O(ℓ 6 ) in genus 2.

Isogenies graph: A possible application of the algorithms presented in this paper is the computation of isogenies graphs. In fact, the Vélu like algorithm of Section 5.1 allows to compute a theta null point 0 A k for a theta structure on A k of level ℓn from a point corresponding to a theta structure of level n.

We can then use the modular correspondence described in Section 2.2, taking an isogeny, to obtain a theta null point 0 C k corresponding to an abelian variety C k with a marking of level n. With this method, it is possible to compute ℓ 2 -isogenies graphs.

In this manner, when we compute a sequence of ℓ 2 -isogenies it is possible to benefit from the computation of the intermediate step 0 A k : since 0 A k is a theta null point of level ℓn, we can recover from it all points in A k [ℓ]. Denote by π 2 : A k → C k the isogeny defined by the modular correspondence. Then K 2 := π 2 (A k [ℓ]) gives half the ℓ-torsion of C k (to get an explicit description of K 2 , just apply I to the results of Section 2.3). Since K 2 is the kernel of the contragredient isogeny of π 2 , we have a way to compute isogeny graph of ℓ 2 -isogenies where the composition of two such isogenies give an ℓ 4 -isogeny and not, for instance if g = 2, a (1, ℓ 2 , ℓ 2 , ℓ 4 )-isogeny (it is enough to consider the isotropic subgroups of C k [ℓ] that intersect K 2 trivially).

The knowledge of K 2 can also be used to speed up the computation of C k [ℓ]. In the following section, we describe an algorithm to compute the Weil pairing e

W on C k [ℓ]. Let (G 1 , • • • , G g ) be a basis of K 2 ,
and consider the system of degree ℓ g +1 given by the ideal of ℓ-torsion and the relations e(G i , •) = 1 (which have a rational expression) for i ∈ [2..g ]. Let H 1 be a point solution of this algebraic system different from < G 1 > (which can be tested be verifying that e W (G 1 , H 1 ) ̸ = 1). We can now construct the system of degree ℓ g given by the ideal of ℓ-torsion and the relations e W (G i , •) = 1 for i ̸ = 2 and e W (H 1 , •) = 1; and look for a solution H 2 such that e(G 2 , H 2 ) ̸ = 1. Continuing this process, we obtain an algorithm to construct a basis G

1 , • • • , G g , H 1 , • • • , H g o f C k [ℓ]
by solving a system of degree ℓ g +1 , then of degree ℓ g , …, then of degree ℓ 2 . This is faster than solving the ideal of ℓ-torsion which is a system of degree ℓ 2 g .

 Pairing computations

In this section, we explain how to use the addition chains introduced in Section 3.2 in order to compute the commutator pairings on abelian varieties. We recall the definition of the commutator pairing and its link with the Weil pairing in Section 6.1.

. Weil pairing and commutator pairing

0 τ * y ′ 0 τ * x 0 τ * x+y ′ 0 ψ y ′ τ * x ψ y ′ ψ x τ * y ′ ψ x
But this is exactly the definition of e ′ W (x, y) thus we have e ′ W (x, y) = e W (x, y).

. Commutator pairing and addition chains

In this paragraph, we explain how to compute the Weil pairing using addition chains. All known algorithms to compute efficiently the Weil pairing on an abelian variety B k are based on a Miller loop [START_REF] Victor | The weil pairing, and its efficient calculation[END_REF] which can be used only in the case that B k is a jacobian. We choose a theta structure Θ B k , 0 for 0 compatible with Θ B k and we let 0 B k ′ be an affine lift of the theta null point corresponding to Θ B k as in Section 5.2. Let x, y ∈ B k [ℓ], and x ′ , y ′ ∈ B k [ℓ 2 ] be such that ℓ.x ′ = y and ℓ.y ′ = y. There exist (α 1 , α 2 ), (β 1 , β 2 ) ∈ Z(ℓ 2 n) × Ẑ(ℓ 2 n) such that (1, α 1 , α 2 ). 0 B k ′ is an affine lift of x ′ and (1, β 1 , β 2 ). 0 B k ′ is an affine lift of y ′ . We note x ′ i = Θ B k , 0 (α i ) and y ′ i = Θ B k , 0 (β i ) for i = 1, 2, we have x ′ = x ′ 1 + x ′ 2 and y ′ = y ′ 1 +y ′ 2 is the decomposition of x ′ and y ′ in the decomposition K( 0 ) = K 1 ( 0 ) × K 2 ( 0 ) into isotropic subspaces induced by the theta structure Θ B k , 0 . Lemma 6.2: Let i ∈ Z(ℓ 2 n) and put s(1) = ((1, α 1 , 0).(1, β 1 , 0).

ϑ i )( 0 B k ′ ) ((1, α 1 , 0). ϑ i )( 0 B k ′ ) . ϑ i ( 0 B k ′ ) ((1, β 1 , 0). ϑ i )( 0 B k ′ )
.

For all k ∈ , we have

s (k) = ((1, k.α 1 , 0).(1, β 1 , 0). ϑ i )( 0 B k ′ ) ((1, k.α 1 , 0). ϑ i )( 0 B k ′ ) . ϑ i ( 0 B k ′ ) ((1, β 1 , 0). ϑ i )( 0 B k ′ ) = s (1) k . ( 31
)
Proof: Consider the degree-0 line bundle Λ = τ * y ′ 1 0 ⊗ -1 0 . We remark that as y ′ 1 ∈ K( 0 ), Λ is isomorphic to the trivial line bundle on B k . Let K be the subgroup of K 1 ( 0 ) generated by x ′ 1 and let C k be the quotient of B k by K. The line bundle Λ descends to a line bundle Λ ′ over C k . As Λ ′ has degree 0, it is the quotient of B k × 1 k by an action of the form g ′ x (t , α) = (t + x, χ 0 (x).α), where (t , α) ∈ B k × 1

x , x ∈ K, and χ 0 is a character of K. As ϑ ∈ H 0 ( 0 ), we remark that f = ((1, β 1 , 0). ϑ)/( ϑ) is a section of Λ ′ . Thus, we have s(k) = f (k.x ′ 1 )/ f (0 B k ) = χ 0 (k) and s(k) = s (1) k .

Remark 6.3:

We remark that in the preceding lemma, α 1 and β 1 play the same role and as a consequence can be permuted. ♦

We keep the notation of the beginning of this paragraph to state the Proposition 6.4:

We put:

L = ((1, ℓ.α 1 + β 1 , ℓ.α 2 + β 2 ) ϑ)( 0 B k ) ((1, β 1 , β 2 ) ϑ)( 0 B k ) . ϑ( 0 B k ) ((1, ℓ.α 1 , ℓ.α 2 ) ϑ)( 0 B k ) . R = ((1, α 1 + ℓ.β 1 , α 2 + ℓ.β 2 ) ϑ)( 0 B k ) ((1, α 1 , α 2 ) ϑ)( 0 B k ) . ϑ( 0 B k ) ((1, ℓ.β 1 , ℓ.β 2 ) ϑ)( 0 B k )
.

We have :

e ℓ 0 (x, y) = L -1 .R. (32)
Proof: First, we compute L. We have:

(1, ℓ.α 1 + β 1 , ℓ.α 2 + β 2 ) ϑ = 〈ℓ.α 1 + β 1 , -ℓ.α 2 -β 2 〉(1, ℓ.α + β 1 , 0)(1, 0, ℓ.α 2 + β 2 ) ϑ = 〈ℓ.α 1 + β 1 -i , -ℓ.α 2 -β 2 〉(1, ℓ.α 1 + β 1 , 0) ϑ.

In the same way, we have:

(1, β 1 , β 2 ) ϑ = 〈β 1 , -β 2 -i〉(1, β 1 , 0) ϑ,

(1, ℓ.α 1 , ℓ.α 2 ) ϑ = 〈ℓ.α 1 , -ℓ.α 2 -i〉(1, ℓ.α 1 , 0) ϑ.

Taking the product, we obtain that L = 〈ℓ.α 1 , -β 2 〉.L ′ , with

L ′ = ((1, β 1 , 0).(1, ℓ.α 1 , 0) ϑ)( 0 B k ) (1, β 1 , 0) ϑ( 0 B k ) ϑ( 0 B k ) (1, ℓ.α 1 , 0) ϑ( 0 B k )
.

In the same manner, we have: R = 〈ℓ.β 1 , -α 2 〉.R ′ , with R ′ = ((1, α 1 , 0).(1, ℓ.β 1 , 0) ϑ)( 0 B k )

(1, α 1 , 0) ϑ( 0 B k )

ϑ( 0 B k )
(1, ℓ.β 1 , 0) ϑ( 0 B k )

.

Using lemma 6.2 and the fact that (1, α 1 , 0) commutes with (1, β 1 , 0) we get that L ′ = R ′ . Therefore, L -1 .R = 〈ℓ.α 2 , β 1 〉 〈ℓ.α 1 , β 2 〉 = e ℓ 0 (x, y).

The preceding proposition gives us an algorithm to compute the pairing: Let P, Q ∈ B k [ℓ], and choose any affine lift P , Q and P + Q, we can compute the following via addition chains: , so that by Proposition 6.4, we have:

0 B k P 2 P . . . ℓ P = λ 0 P 0 B k Q P + Q 2 P + Q . . . ℓ P + Q = λ 1 P Q 2 Q P + 2 Q . . . . . . ℓ Q = λ 0 Q 0 B k P + ℓ Q = λ
e ℓ 0 (P, Q) = λ 1 P λ 0 Q λ 1 Q λ 0 P 40
Now by Lemma 3.10, it is easy to see that (33) is homogeneous and does not depend on the affine lifts P , Q and P + Q, which concludes the proof.

Complexity Analysis 6.6: By using a Montgomery ladder, we see that we can compute e ℓ 0 (P, Q) with four fast addition chains of length ℓ, hence we need O(log(ℓ)) additions. It should be noted that we can reuse a lot of computation between the addition chains P, 2P, 4P, . . . and P + Q, 2P + Q, 4P + Q, . . . since we always add the same point at the same time between the two chains.

 Conclusion

We have described an algorithm that give a modular point from an isotropic kernel, and another one that can compute the isogeny associated to a modular point. By combining these two algorithms, we can compute any isogeny between abelian varieties. However, the level of the modular space that we use depend on the degree of the isogeny. Still, we can go back to a modular point of level n by using the modular correspondence introduced in [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF]. This mean that we can compute isogeny graphs if we restrict to ℓ 2 -isogenies. We have also introduced a point compression algorithm, that allows to drastically reduce the number of coordinates of a projective embedding of level 4ℓ. This new representation can be useful when one has to work with such a projective embedding, rather than the usual one of level 4 (for instance if one need a quick access to the translation by a point of ℓ-torsion).

  of (B k , 0 , Θ B k , 0 ) where 0 = [ℓ] * 0 and Θ B k , 0 is a theta structure on (B k , 0 ) compatible with Θ B k . 31 [ℓ] [ℓ] : B k ′ → B k is the morphism lifting [ℓ] : B k → B k . 31 chain_addAn addition chain 15 chain_multadd A multiplication chain 18

  ℓn), and we always consider the compatible theta structure on B k corresponding to σ = Id [FLR09, Sec. 3]. We recall the following proposition [FLR09, Prop 4].

:

  Algorithm 3.6 (Multiplication chain): Input m ∈ , x + y, x, y ∈ A k . Output chain_multadd(m, x + y, x, y). Compute the binary decomposition of m := I i=0 b i 2 i . Set m ′ := 0, xy 0 := y, xy -1 := chain_add( y, -x, x + y), x 0 := 0 A k and x 1 := x. : For i in [I ..0] do If b i = 0 then compute

  (n, λ x+y x + y, λ x x, λ y y) = x + y, x, y),(16) chain_mult(n, λ x x) = λ n 2x chain_mult(n, x).

  •, i + j ) = e(•, k + l ) (as characters on Z(2)) if and only if there exists m ∈ Z(ℓn) such that i + j + k + l = 2m. Now since I + J + K + L = 2M we have e(I + J , •) = e(K + L, •) and as a consequence: λ t 1 ,t 2 ∈Z(2)

Since

  B k [ℓ] ⊂ K( 0 ) ℓ the commutator pairing e ℓ 0 gives a non degenerate pairing on B k [ℓ] (if n is prime to ℓ), we call e ℓ 0 the extended commutator pairing on B k [ℓ]. We can give another interpretation of this pairing, more suitable for computation: let 0 = [ℓ] * 0 on B k . We know that 0 ⊗ (τ * y ′ 0 ) -1 . We remark that the isomorphism ψ ′ y : [ℓ] * Λ y = 0 ⊗ (τ * y ′ 0 ) -1 → B k gives by tensoring on the right by τ * y ′ 0 an isomorphism ψ y ′ : 0 → τ * y ′ 0 . Thus, the following diagram is commutative up to a multiplication by e W (x, y):

Algorithm 6. 5 (

 5 Pairing computation):Input P, Q ∈ B k [ℓ]

::

  Namely we compute:ℓ P := chain_mult(ℓ, P ) ℓ Q := chain_mult(ℓ, Q) ℓ P + Q := chain_multadd(ℓ, P + Q, P , Q) P + ℓ Q := chain_multadd(ℓ, P + Q, Q, P ). Then we have: Assume that P , Q and P + Q are such that P = [ℓ](1, α 1 , β 1 ) 0 ′ B k , Q = [ℓ](1, α 2 , β 2 ) 0 ′ B k , and P + Q = [ℓ](1, α 1 +α 2 , β 1 +β 2 ) 0 ′ B k. Then by Corollary 24,we find thatλ 0 P = ϑ( 0 B k ) ((1,ℓ.α 1 ,ℓ.α 2 ) ϑ)( 0 B k ) = 1 and that λ 1 P = ((1,ℓ.α 1 +β 1 ,ℓ.α 2 +β 2 ) ϑ)( 0 B k ) ((1,β 1 ,β 2 ) ϑ)(0)

The case n = 2

 2 Let ±P, ±Q ∈ K B , then we have e ℓ 0 (±P, ±Q) = {e ℓ 0 (P, Q), e ℓ 0 (P, Q) -1 }. Thus the pairing on the Kummer variety is a bilinear pairing K B × K B → k * ,± where k * ,± = k * /{x = 1/x}. We represent a class x ∈ k * ,± by x+1/x ∈ k,and we define the symmetric pairing e ′ s (±P, ±Q) = e ℓ 0 (P, Q) + e ℓ 0 (P, -Q). We can use the addition relations to compute P ± Q and then use Algorithm 6.5 to compute e ℓ 0 (P, Q), e ℓ 0 (P, -Q).

  One can check that this theta structure is compatible with the isogeny ξ [Mum66, p. 325]. Applying the isogeny theorem (see [Mum66, p. 324]), we obtain that there exists λ ∈ k

there exists a theta structure Θ 2 on 2 such that Θ 2 and Θ are compatible in the sense of

Mumford [Mum66, p. 317

]. The theta structure Θ 2 then induces a theta structure Θ 2 on 2 . * such that for all i, j ∈ Z(ℓn):

Theorem 4.8: Let y ∈ B k (k) and let x ∈ A k (k) be such that π( x) = y. For all i ∈ Z(ℓ),

where λ ℓ i is determined by: y = λ ℓ i chain_multadd(ℓ, π a i (x), R i , y).

Proof: By Proposition 3.11 and Lemma 3.10 we have:

Now we only need to find the λ ℓ i for i ∈ Z(ℓ). But by Proposition 3.11 and an easy recursion, we have x = s K 1 ( ) (i) ℓ . x so that by Corollary 3.12 and Lemma 3.10 π( x) = chain_multadd(ℓ, π i ( x), R i , y) = λ ℓ i . chain_multadd(ℓ, π a i (x), R i , y).

Remark 4.9:

We can use the preceding theorem recover the equations of the isogeny by taking for y the generic point of B k . ♦

Algorithm 4.10 (The image of a point by the isogeny):

Output The compressed coordinates of π(y) ∈ A k (k).

: For each i ∈ S

• (Step 1) Compute y + R i and choose an affine lift y i of y + R i .

• (Step 2) Compute ylR i := chain_multadd(ℓ, y i , R i , y 0 ) Let λ i be such that y 0 = λ i ylR i . • Output λ i chain_multadd(ℓ, y i , y 0 , R i )).

Correction and Complexity Analysis 4.11:

Let y = y 0 , and x ∈ A k (k) be such that π( x) = y, and let z = ℓ x. Then p A k ( z) = π(y) and we note z = π( y).

In the Output, Theorem 4.8 show that we compute π i ( π( y)) = λ ℓ i chain_multadd(ℓ, y i , y 0 , R i )) since λ ℓ i is given in Step 2 by y 0 = λ ℓ i chain_multadd(ℓ, y i , R i , y). We can easily recover π(y) from the π i ( π( y)), i ∈ Z(ℓ), but we note that it is faster to compute the π i ( π( y)) only for i ∈ S (with the notations of Example 4.3 in the preceding section). and then use Algorithm 4.7 to obtain the full coordinates of π(y). This last step is unnecessary if we only need the compressed coordinates of π(y).

To compute π i ( π( y)), we need to do two multiplication chains of length ℓ. We obtain the compressed coordinates of ℓ.x after g (g + 1)/2 such operations. In total we can compute the compressed coordinates of a point in O( 1 2 g (g + 1) log(ℓ)) additions in B k (with 1 2 g (g + 1)n g divisions in k) and the full coordinates in O(ℓ g ) additions in B k .

By the Remark at the end of Lemma 5.4, we may suppose that i 3 = i 1 -i 2 , j 3 = j 1 -j 2 . Since y 1 , y 2 and y 1 -y 2 are excellent points of ℓ-torsion, by Remark 5.3 and Lemma 5.4 we may suppose that

By Corollary 24 and Lemma 3.10, we have

so y 1 + y 2 is indeed an excellent point of ℓ-torsion by Lemma 5.4.

. Improving the computation of a modular point

In [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF], to compute the modular points 0 A k , the following algorithm is used:

, consider the algebraic system S defined by the Riemann and symmetry relations (3) with (a i ) i ∈Z(ℓn) considered as unknown and where we put a i = b i for i ∈ Z(n). The algebraic system S define a 0dimensional algebraic variety which contains the set of modular points 0 A k . We then present algorithm to compute efficiently a Gröbner basis of the system S.

In this section, in order to improve the algorithm of [START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF], we explain how, using the "Vélu's"-like formulas of Section 5.1, it is possible to recover all the modular points 0 A k solution of the system S from the knowledge of the ℓ-torsion of B k . We then discuss different methods to compute the ℓ-torsion in B k .

Algorithm 5.6 (Computing all modular points):

We only give an outline of the algorithm, since we give a detailed description in Example 5.7. We suppose that we know how to compute e ℓ 0 on B k [ℓ]. We will explain how to do this in the next section. Example 5.7:

(A symplectic basis is easy to obtain from a basis of the ℓ-torsion, we just need to compute the discrete logarithms of some of the pairings between the points, where the pairings can be computed with Algorithm 6.5).

Let Θ B k , 0 be any theta structure of level ℓ 2 n on B k compatible with Θ B k , and 0 ′ B k be the corresponding theta null point (see Section 5.2). We may suppose (see Section 5.1) that

Then by Corollary 24, using Algorithm 5.6, we compute the following affine lifts of the ℓ-torsion:

is an isotropic group, in the reconstruction algorithm 5.1 we need to compute points of the form

, where α, β ∈ Z(ℓ 2 n), and ζ is a (ℓ 2 n) t h -root of unity. As a consequence, we can always go back to a point computed in (30) up to an ℓ t h -root of unity. We give a detailed example with g = 1, ℓ = 3, n = 4. Let B k be an elliptic curve, with a theta structure Θ B k of level n. Let T 1 , T 2 be a basis of B k [ℓ], and choose excellent affine lifts T 1 , T 2 , T 1 + T 2 .

Let Θ B k , 0 be any theta structure of level ℓ 2 n compatible with Θ B k , and 0 ′ B k be the corresponding theta null point (see Section 5.2). We take

and

We have seen in (30) that in the Algorithm 5.6 we compute the points:

choose a compatible theta structure Θ A k on A, and let 0 A k be the associated theta null point.

As usual, we define R i = π i ( 0 A k ) if i ∈ /ℓZ ⊂ /ℓn , and we may suppose (Section 5.1) that Θ A k is such that R 1 = T . More explicitly, if n = 4 we have (Remember that we always choose 0 A k such that π( 0 A k ) = 0 B k ): 0 A k = (a 0 , a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 , a 10 , a 11 ) π(x 0 , x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 , x 9 , x 10 , x 11 ) = (x 0 , x 3 , x 6 , x 9 ) R 0 = (a 0 , a 3 , a 6 , a 9 ) = 0 B k R 1 = (a 4 , a 7 , a 10 , a 1 ) R 2 = (a 8 , a 11 , a 2 , a 5 ) Now by Theorem 4.4 we know that 0 A k is entirely determined by R 1 (and 0 B k ), in fact we have:

This shows that in the reconstruction step, we have to multiply the point [ℓ](1, 2n, n). 0 ′ B k which we have already computed by the ℓ-root of unity ζ 2n•ℓn .

Complexity Analysis 5.8:

To compute an affine lift T i , we have to compute an ℓ t h -root of unity (and do some addition chains but we can reuse the results for the next step). Once we have computed the ℓ(2ℓ + 1) t h -root, we compute the whole (affine lifts of ) ℓ-torsion by using O(ℓ 2g ) addition chains. We can now compute the pairings e(T i , T j ) with just one division since we have already computed the necessary addition chain (see Section 6). From these pairings we can compute a symplectic basis of B k [ℓ]. This requires to compute the discrete logarithm of the pairings and can be done in O(ℓ) time. Using this basis, we can enumerate every isotropic subgroup K ⊂ B k [ℓ], and reconstruct the corresponding theta null point with O(ℓ g ) multiplications by an ℓ t h -root of unity.

The case (n, ℓ > 1) In this case, the only difference is that we have to compute B k [ℓn] rather than B k [ℓ], and when T i is a point of ℓn-torsion, we compute an affine lift T i such that:

The case n = 2: This works as in Section 5.1, once we have computed the T e 1 + T e i , we have to take compatible additions to compute the T e i + T e j .

Computing the points of ℓ-torsion in B k : By applying the addition relations of Section 3.2 on the generic point of B k , we obtain an algebraic system of equations of degree ℓ 2 g in n g unknown defining B k [ℓ]. We can compute the solutions of this system by using the general purpose Gröbner basis computation algorithm.

In general we prefer to work with Kummer surfaces (so with n = 2), since it cuts the degree of the system by two. In genus 2, Gaudry and Schost [START_REF] Gaudry | Hyperelliptic curve point counting record: 254 bit jacobian, 06[END_REF] have an algorithm to compute the ℓ-torsion on the Kummer surface using resultants rather than a general purpose Gröbner basis algorithm. The K( 0 ) is isomorphic to K(ℓ 2 n) (see Section 5.2). As 0 descends to 0 via the isogeny [ℓ], the commutator pairing e 0 induced by the polarization 0 is trivial on The following proposition is well known Proposition 6.1:

The pairing e ′ W is the Weil pairing e W . Proof: A proof can be found in [START_REF] Mumford | Abelian varieties[END_REF]p. 228]. We give here a quick proof using the definition of e ℓ 0 given in term of the polarization 0 since it will be instructive for our algorithm in Section 6.2.

For y ∈ Bk [ℓ], we denote by Λ y the degree-0 line bundle on B k associated to y. A possible definition of the Weil pairing e W is as follows:

. By definition [START_REF] Mumford | Abelian varieties[END_REF], we have e W (x, y) = χ (x).

We can reformulate this definition as follow: we choose an isomorphism B k (0) ≃ k from which we deduce via ψ ′ y (resp. τ * x ψ ′ y ) an isomorphism ψ 0 : [ℓ] * Λ y (0) ≃ k (resp. ψ 1 : τ * x [ℓ] * Λ y (0) ≃ k). There exists a unique isomorphism ψ x : [ℓ] * Λ y → τ *

x [ℓ] * Λ y compatible on the 0 fiber with ψ 0 and ψ 1 , i.e. we have that ψ 1 • ψ x • ψ -1 0 is the identity of k. Then, the following diagram commutes up to a multiplication by e W (x, y): The polarization 0 gives the natural isogeny ϕ 0 , defined on geometric points by

As a consequence, for y ∈ Bk [ℓ] there exists y 0 ∈ B k (k) such that Λ y = 0 ⊗ (τ * y 0 0 ) -1 . Let y ′ ∈ B k [ℓ 2 ] be such that ℓ.y ′ = y 0 . As [ℓ] * 0 = 0 , we have [ℓ] * Λ y = [ℓ] * ( 0 ⊗ (τ * y 0 0 ) -1 ) =