Romain Cosset

Damien Robert

COMPUTING ( , )-ISOGENIES IN POLYNOMIAL TIME ON JACOBIANS OF GENUS 2 CURVES

In this paper, we compute -isogenies between abelian varieties over a field of characteristic different from 2 in polynomial time in , when is an odd prime which is coprime to the characteristic. We use level n symmetric theta structure where n = 2 or n = 4. In a second part of this paper we explain how to convert between Mumford coordinates of Jacobians of genus 2 hyperelliptic curves to theta coordinates of level 2 or 4. Combined with the preceding algorithm, this gives a method to compute ( , )-isogenies in polynomial time on Jacobians of genus 2 curves.

Introduction

The discrete logarithm problem on the group of rational points of an elliptic curve E/F q is believed to be hard (except for some special families of elliptic curves [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF][START_REF] Gaudry | Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem[END_REF]. . . ). In fact, if #E(F q ) is a prime p, then the best known algorithm to solve the DLP in E(F q ) is the generic Pollard-rho algorithm in O( √ p). Thus in recent years [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF], elliptic curves have been used in public key cryptography. Moreover, there exist natural pairings on elliptic curves, which allow for the construction of many new and interesting protocols [START_REF] Joux | A one round protocol for tripartite Diffie-Hellman[END_REF][START_REF] Boneh | Short signatures from the Weil pairing[END_REF][START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF][START_REF] Verheul | Self-blindable credential certificates from the Weil pairing[END_REF][START_REF] Sahai | Fuzzy identity-based encryption[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF]. Another solution is to work over the group of rational points of the Jacobian of a curve C defined over F q (or even any abelian variety). If the genus g of C is strictly greater than 2, we have better algorithms than Pollard-ρ to solve the DLP on the Jacobian of C [START_REF] Enge | An L(1/3) discrete logarithm algorithm for low degree curves[END_REF] (these algorithms are still exponential in the largest prime dividing the group when the genus is not too large). Jacobians of genus 2 curves are particularly interesting since they allow the same security as with elliptic curves, while working with fields of half the size.

In the genus 2 case, we still lack some of the efficient algorithms that we have for elliptic curves. One of them is the efficient computation of isogenies. They are used in the elliptic curves case for the construction of Hilbert class polynomials [START_REF] Sutherland | Computing Hilbert class polynomials with the Chinese remainder theorem[END_REF], for endomorphism ring computations [START_REF] Kohel | Endomorphism rings of elliptic curves over finite fields[END_REF][START_REF] Fouquet | Isogeny volcanoes and the SEA algorithm[END_REF][START_REF] Bisson | Computing the endomorphism ring of an ordinary elliptic curve over a finite field[END_REF], for modular polynomials [START_REF] Bröker | Modular polynomials via isogeny volcanoes[END_REF], and they form a basic ingredient of the amelioration by Atkin and Elkies of the Schoof point counting algorithm [START_REF] Schoof | Elliptic curves over finite fields and the computation of square roots mod p[END_REF][START_REF] Schoof | Counting points on elliptic curves over finite fields[END_REF][START_REF] Atkin | The number of points on an elliptic curve modulo a prime[END_REF][START_REF] Elkies | Explicit isogenies[END_REF]. For elliptic curves, one can compute isogenies using Vélu's formulae and modular polynomials (the latter are more suited for the computation of isogeny graphs). For higher dimensional abelian varieties, Richelot formulae [START_REF] Richelot | Essai sur une méthode générale pour déterminer la valeur des intégrales ultraelliptiques, fondée sur des transformations remarquables de ces transcendantes[END_REF][START_REF] Richelot | De transformatione Integralium Abelianorum primiordinis commentation[END_REF] allow to compute [START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF][START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF]-isogenies between Jacobians of genus 2 curves, and [START_REF] Smith | Isogenies and the discrete logarithm problem in jacobians of genus 3 hyperelliptic curves[END_REF] give an algorithm to compute (2, 2, 2)-isogenies between Jacobians of genus 3 curves. In [START_REF] Bröker | Explicit CM-theory in dimension[END_REF], the authors explain how to compute [START_REF] Bisson | Computing the endomorphism ring of an ordinary elliptic curve over a finite field[END_REF][START_REF] Bisson | Computing the endomorphism ring of an ordinary elliptic curve over a finite field[END_REF]-isogeny graphs of abelian varieties of dimension 2 (but not the explicit form of the isogenies) using theta constants of level 4. A generalisation of Vélu's formulae is given in [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF], which describes algorithm which takes for input a basis of a maximal isotropic subgroup K of an abelian variety A and outputs the isogeny A → A/K is described. One drawback of this algorithm is that it needs to work with theta functions of different levels on A and on A/K. The authors also describe an algorithm to compute isogenies while working on theta functions of a fixed level n, but it only allows to compute 2 -isogenies. In this paper, we show how one can use the addition formulae from Koizumi [START_REF] Koizumi | Theta relations and projective normality of abelian varieties[END_REF] to obtain an explicit algorithm for the conversion of theta coordinates of different level. Combined with the algorithm of [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF], this yields an algorithm to compute -isogenies between abelian varieties described by theta coordinates of the same level n: Theorem 1.1. Let (A k , L, Θ n ) be a polarised abelian variety of dimension g with a symmetric theta structure of level n (since L is totally symmetric, n is even). Let be prime to n and assume that the characteristic of k is prime to n. Let K be a maximal isotropic subgroup of A[ ] (for the pairing induced by the polarisation L). Then we can compute the isogeny A → A/K in theta coordinates of level n by using O( rg 2 ) arithmetic operations in k , where k is the field extension where the theta coordinates of the geometric points of K are defined, and r = 2 if ≡ 1 mod 4, r = 4 otherwise.

One drawback of using theta functions of level n is that they are not rational. If C is an hyperelliptic curve of genus g, Mumford coordinates give rational coordinates on the Jacobian of C. In the second part of this paper, we focus on the genus 2 case. Thomae's formulae only give the fourth power of the coordinates of the theta null point of level 4. When g = 2, we show how to take canonical roots up to the action of PSp(4, Z) in Section 5.1. We describe formulae to convert between Mumford coordinates on the Jacobian of an hyperelliptic curve of genus 2 and theta coordinates of level 2 and 4. Combined with Theorem 1.1 we obtain: Theorem 1.2. Let J be the Jacobian of an hyperelliptic curve of genus 2 over a field k of characteristic different form 2. Let K be a maximal isotropic subgroup of J[ ] for the Weil pairing. Then we can compute the isogeny J → J/K in Mumfod coordinates by using O( r ) arithmetic operations in k , where k is the field extension where the Mumford coordinates of the geometric points of K are defined, and r = 2 if ≡ 1 mod 4, r = 4 otherwise.

In particular, if k is a finite field, and K is rational, then we can compute the isogeny using O( 2+r ) arithmetic operations in k.

Theorem 1.1 is proved in Section 4 and Theorem 1.2 is proved in Section 5. For simplicity, we assume that we work over a subfield k of C. However our formulae and algorithms apply to any field (of characteristic different from 2). To prove the formulae over a finite field (the cryptographically relevant case), if the abelian variety is ordinary we can consider its canonical lift and invoke Lefschetz's principle. To prove them over any field (and relax the ordinary condition), we can use Mumford theory of algebraic theta functions [START_REF] Mumford | On the equations defining abelian varieties[END_REF][START_REF] Mumford | On the equations defining abelian varieties[END_REF][START_REF] Mumford | On the equations defining abelian varieties[END_REF]. We then need an algebraic version of Koizumi's addition formulae [START_REF] Koizumi | Theta relations and projective normality of abelian varieties[END_REF] given by Kempf [START_REF] Kempf | Linear systems on abelian varieties[END_REF]. The reader interested to an algebraic proof is referred to [START_REF] Robert | Theta functions and applications in cryptography[END_REF]Section 7.8].

For the convenience of the reader, we try to be as self contained as possible, so rather than just explaining how to use Koizumi's addition formulae to change the level of theta coordinates and refer to [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF], we describe the full isogeny algorithm. In Section 2 we recall some well known facts about analytic theta functions, and describe the basis of theta functions we are going to use through the paper. Section 3 gives Koizumi's addition formulae, and as a first application how one can use them to obtain an algorithm for differential additions. The isogeny computation is described in Section 4, and the special case of Jacobians of genus 2 hyperelliptic curves where we have complete formulae for the conversion between Mumford and theta coordinates is treated in Section 5. Some of these formulae are quite lengthy, and given in the Appendix.

Theta coordinates on abelian varieties

Over C, an abelian variety A of dimension g is analytically isomorphic to a torus C g /(ΩZ g + Z g ) where Ω is an element of the Siegel half-space H g :

H g = {Ω ∈ M g×g (C), t Ω = Ω and (Ω) > 0}.
There is a canonical principal polarisation L associated to the choice of Ω and given by the Riemann form [START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF]. We will call a section of L n a theta function of level n.

E(Ωx 1 + x 2 , Ωy 1 + y 2 ) = t x 1 y 2 -t y 1 x 2 on ΩZ g + Z g
We recall that the classical Riemann theta function associated to Ω is an analytic function from C g to C. It is defined by [START_REF] Mumford | Tata lectures on theta I[END_REF] Θ(z, Ω) =

n∈Z g exp πi t nΩn + 2πi t nz .
For a, b ∈ Q g , the theta function of characteristics a, b is a translation of the classical theta up to an exponential factor:

(1) Θ [ a b ] (z, Ω) = Θ(z + Ωa + b, Ω) exp πi t aΩa + 2πi t a(z + b) . These characteristics can be considered modulo Z 2g since for α, β in Z g we have

Θ a+α b+β (z, Ω) = Θ [ a b ] (z, Ω) exp(2πi t aβ).
A basis of the theta functions of level n is given by [START_REF] Mumford | Tata lectures on theta I[END_REF]

Θ [ 0 b ] (z, Ω n ) b∈ 1 n Z g /Z g .
To ease the notations, we note Z(n) = Z g /nZ g , and we fix once and for all a section

Z(n) → Z g . We then define for b ∈ Z(n): θ b := Θ 0 b n •, Ω n . When n = k 2 ,
another choice for the basis of level n theta functions is given by

(Θ [ a b ] (kz, Ω)) a,b∈( 1 k Z g )/Z
g . We will call this the basis of level (k, k). The linear transformations between the basis of level n = k 2 and the basis of level (k, k) are given by [START_REF] Mumford | Tata lectures on theta I[END_REF]:

Θ a/k b/k (kz, Ω) = 1 k g β∈Z g /kZ g exp -2πi t ab k Θ 0 b/n+β/k z, Ω n , Θ 0 b/n z, Ω n = α∈Z g /kZ g Θ α/k b/k (kz, Ω).
The advantage of the latter choice is that it comes more naturally as analytic functions over the abelian variety. On the other hand, the formers are more general and "symmetric":

θ i (-z) = θ -i (z).
A well known result of Lefschetz states that when n ≥ 3, the theta functions of level n give a projective embedding:

ϕ L : C g /(Z g + ΩZ g ) -→ P n g -1 (C) z -→ (θ i (z)) i∈Z(n)
.

When n = 2, and the abelian variety is simple, then the theta functions of level 2 give a projective embedding of the Kummer variety

K A = A/ ± 1. The point (θ i (0)) i∈Z(n) = ϕ L (0 A ) ∈ P n g -1 (C) is called the theta null point (of level n) of A. This point determines (ϕ L (A), ϕ L (A[n]
)) [START_REF] Mumford | On the equations defining abelian varieties[END_REF].

For arithmetic reasons we want to deal with theta functions of level as small as possible. The reason is that if A is defined over a subfield K 0 ⊂ C, a necessary condition for the theta functions of level n to be generated by a basis defined over K 0 is that there exists a K 0 -rational symplectic isomorphism between A[n] (with the induced Riemann form) and Z(n) ⊕ Ẑ(n), where Ẑ(n) is the Cartier dual of Z(n). Here, if µ n is the group of n-roots of unity in C * , then Ẑ(n) = ⊕ g i=1 µ n . Since we will heavily use the duplication formulae (and the Riemann relations), we need 2 | n. For these reasons, in this article, we only work with n = 2 or n = 4. The case n = 2 is a bit more tricky since we work over the Kummer variety, but it is worthwhile in practice.

The addition formulae

An extension of the usual Riemann relations between theta functions is given in a general form by [START_REF] Koizumi | Theta relations and projective normality of abelian varieties[END_REF]Theorem 1.3]: Theorem 3.1 (Koizumi). Let (γ 1 , . . . , γ r ) ∈ Q r , (δ 1 , . . . , δ r ) ∈ Q r and F ∈ Gl r (Q) be such that

t F    γ 1 0 . . . 0 γ r    F =    δ 1 0 . . . 0 δ r    .
Let (x 1 , . . . , x r ) ∈ (C g ) r , and (y 1 , . . . , y r ) = (x 1 , . . . , x r )F . Let (a 1 , . . . , a r ) and (b 1 , . . . , b r ) be elements of (C g ) r , and note

(a 1 , . . . , a r ) = (a 1 , . . . , a r ) t F -1 , (b 1 , . . . , b r ) = (b 1 , . . . , b r )F. Let d be the index [M g×r (Z) + M g×r (Z) t F : M g×r (Z)]
We have:

(2) d Θ a1 b1 (x 1 , γ 1 Ω) × • • • × Θ ar br (x r , γ r Ω) = Θ a 1 +α1 b 1 +β1 (y 1 , δ 1 Ω) × • • • × Θ a r +αr b r +βr (y r , δ r Ω)
where the sum is over the elements α and β such that

α ∈ M g×r (Z) t F -1 / M g×r (Z) M g×r (Z) t F -1 , β ∈ M g×r (Z)F/ M g×r (Z) M g×r (Z)F .

Corollary 3.2 (Riemann relations).

Recall that for b ∈ Z(n), we have defined

θ b := Θ 0 b n •, Ω n . Let x 1 , y 1 , u 1 and v 1 in C g such that x 1 + y 1 + u 1 + v 1 = 2z. We define x 2 = z-x 1 , y 2 = z-y 1 , u 2 = z-u 1 and v 2 = z-v 1 . For all i, j, k, l, m ∈ Z(n) with i + j + k + l = 2m, if we let i = m -i, j = m -j, k = m -k and l = m -l
then for all characters χ ∈ Ẑ(2) we have:

(3) 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 ) .
As a particular case, if x, y ∈ C g , we have the following differential addition formulae:

(4) t∈Z( 2)

χ(t)θ i+t (x + y)θ j+t (x -y) . t∈Z(2) χ(t)θ k+t (0)θ l+t (0) = t∈Z(2) χ(t)θ -i +t (y)θ j +t (y) . t∈Z(2) χ(t)θ k +t (x)θ l +t (x) .
Proof. Equation ( 3) is a modified form of the usual Riemann relations obtained from Theorem 3.1 with the matrix

F = 1 2     1 1 1 1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 1     .
The usual Riemann relations can be found in [28, p. 212], and the transformation that gives (3) in [25, p. 334-335].

Assume we are in level 4. As was shown in [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF], one can use the differential addition formulae (4) to compute (θ i (x + y)) i∈Z(n) when x, y ∈ C g , provided one knows (θ i (x)) i∈Z(n) , (θ i (y)) i∈Z(n) , (θ i (x -y)) i∈Z(n) . Indeed, for sufficiently many χ ∈ Ẑ(2), k, l ∈ Z(n), we have t∈Z(2) χ(t)θ k+t (0)θ l+t (0) = 0. It is also possible to compute "normal" additions, that is the addition law on the abelian variety. Suppose that we know the theta coordinates x, y ∈ A = C g /(Z g + ΩZ g ). Here we are working modulo the lattice and we see the theta coordinates as projective coordinates. But the addition formulae allows to recover (θ i (x + y)) i∈Z(n) up to a projective factor, so we can indeed compute normal additions.

When the level n is 2, then the embedding of the Kummer variety K A given by the theta functions of level 2 is projectively normal if and only if the even theta constants

Θ a/2 b/2 0, 2 Ω n | a, b ∈ Z(2), (-1) t a•b = 1
are not zero. In this case, we can also always compute differential additions in level 2 [START_REF] Lubicz | Efficient pairing computation with theta functions[END_REF]. Moreover, when we know ±P ∈ K A , ±Q ∈ K A and the even theta constants are not zero, we can use formulae (4) to recover {±(P + Q), ±(P -Q)} ⊂ K A with a square root. We note that this condition excludes Jacobians of hyperelliptic curves of genus g ≥ 3, we thus have to work with n = 4 to treat them. A small technical detail is that in the algebraic setting, an abelian variety will be represented by its theta null point given in projective coordinates. Thus in practice we will work on it with theta coordinates of the form θ b = λΘ

0 b n •, Ω
n where λ is a projective factor. But since Theorem 3.1 is homogeneous, all our algorithms remain valid in this case.

Computing -isogenies between abelian varieties

In this section, we show how we can improve the results of [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF] by using Theorem 3.1. We will give an algorithm to compute the isogeny

f : A = C g /(ΩZ g + Z g ) -→ B = C g /( ΩZ g + Z g ) z -→ .z
, provided that we know its kernel 1 Z g /Z g . A maximal isotropic subgroup K of the -torsion is isomorphic to 1 Z g /Z g . We want to compute the isogeny associated to K. Let Λ = ΩZ g + Z g be the lattice associated to A. The choice of Ω ∈ H g is equivalent to the choice of a symplectic basis of Λ for the Riemann form (see also Section 5.1). If K is any maximal isotropic subgroup of A[ ] (for the induced Riemann form), then we can always choose a symplectic basis of Λ such that if Λ = Ω 0 Z g + Z g is the corresponding decomposition, we have K = 1 Z g /Z g [START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF][START_REF] Faugère | Computing modular correspondences for abelian varieties[END_REF]. Thus we can apply the preceding algorithm to compute the isogeny associated to any maximal isotropic subgroup.

We proceed in two steps: we first explain how to compute the theta null point of level n of B, and then how to compute f (x) where x is a geometric point in A.

For simplicity, we assume here that n = 4, we will then discuss how to make the necessary adjustments when n = 2. To simplify the notations, we let as in Section 2 for b ∈ Z(n):

θ A b := Θ 0 b n •, Ω n , θ B b := Θ 0 b n •, Ω n .
Let F be a matrix of rank r such that t F F = Id r . If = a 2 + b 2 , we can take

F = a b -b a and r = 2.
In general, we can always write = a 2 + b 2 + c 2 + d 2 and take the matrix of multiplication by a + bi + cj + dk in the quaternions algebra over R, so r = 4. With these notations, we get as a particular case of Theorem 3.1:

Proposition 4.1. Let F be a matrix of rank r such that t F F = Id r . Let X in (C g ) r and Y = XF -1 ∈ (C g ) r . Let i ∈ (Z(n)) r and j = iF -1 . Then we have (5) θ B i1 (Y 1 ) . . . θ B ir (Y r ) = t1,...,tr∈ 1 Z g /Z g (t1,...,tr)F =(0,...,0) θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r ),
Proof. This is a special case of Theorem 3.1 applied to 1 t F , and with (a 1 , . . . , a r ) = (0, . . . , 0), remembering that Θ [START_REF] Atkin | The number of points on an elliptic curve modulo a prime[END_REF]. We explain how to use these formulae to compute explicitly the isogeny.

0 b+β x, Ω n = Θ [ 0 b ] x + β, Ω n by

4.1.

Computing the theta null point of B. Now we assume that we know the coordinates of a basis (e 1 , . . . , e g ) of K in A. Up to a symplectic change of basis, we can assume that this basis is the reduction of the canonical basis (ẽ 1 , . . . , ẽg ) of 1 Z g to A. This mean that we know the coordinates (θ A k (ẽ i )) k∈Z(n) up to an unknown projective factor λ i for i = 1, . . . , g.

Since we are assuming n = 4, we can compute e i + e j ∈ A for i = j ∈ [1, g], so that we know θ A k (ẽ i + ẽj ) up to an unknown projective factor λ ij . Now by using the Riemann relations, we can compute all the points θ A k (n 1 ẽ1 + . . . n g ẽg ) exactly in terms of the λ i and λ ij .

We detail this step. First, it is important to note that the result does not depend on the order of the Riemann relations used to compute a point of the form θ A k (n 1 ẽ1 + . . . n g ẽg ) . Indeed, the same proof as in [22, Lemma 2] applies here. Now, if we had all the coordinates θ A k (n 1 ẽ1 + . . . n g ẽg ) with n k ∈ {0, 1} for k = 1, . . . , g, we could use differential additions to compute the rest. To get these coordinates we can proceed as follow: assume for example that g = 3. Then by using differential additions, we can compute ẽ1 -ẽ3 . We can then use a differential addition on ẽ1 + ẽ2 and ẽ2 + ẽ3 to compute ẽ1 + 2ẽ 2 + ẽ3 . Since is odd, we can use differential additions to compute ẽ1 + ( + 1)ẽ 2 + ẽ3 . Using this method, we can compute an affine lift of any element in the kernel. We need some care with this method, because the polynomial given by ẽ1 + ( + 1)ẽ 2 + ẽ3 differs from the one given by ẽ1 + ẽ2 + ẽ3 by a factor in C[λ i , λ ij ]. This is not a problem for the rest of the algorithm, as we can keep track of this factor, and as we will see the -th power of the λ i are known.

Perhaps an easier way is to use more general Riemann relations than the ones coming from the differential additions. For instance by setting 3), we can compute directly the (affine) theta coordinates of ẽ1 + ẽ2 + ẽ3 in terms of the theta null point and the theta coordinates of ẽ1 , ẽ2 , ẽ3 , ẽ2 + ẽ3 , ẽ1 + ẽ3 , ẽ1 + ẽ2 . We will call this an extended differential addition. With this method, we need to be sure that sufficiently many elements of the form t∈Z( 2) χ(t)θ k+t (ẽ 2 )θ l+t (ẽ 3 ) are not zero, so that we can indeed compute the extended differential addition. This follows from the fact that since we are working with an isotropic kernel, we can interpret the theta coordinates of level n of points of this kernel as the theta coordinates of level n of the theta null point of an -isogenous abelian variety (for the proof, see [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF]Section 3.3]).

x 1 = ẽ1 + ẽ2 + ẽ3 , y 1 = ẽ1 , u 1 = ẽ2 , v 1 = ẽ3 , in equation (
We can also recover some informations on the λ i , λ ij . Indeed, write = 2 + 1.

Then we have θ

A k (( + 1)ẽ i ) = θ A -k ( ẽi ) since ( + 1)ẽ i = -( )ẽ i modulo Z g and the θ A
k are invariants by translation by an element in Z g . In terms of the λ i , we get an equation of the form λ

( +1) 2 i = α i λ ( ) 2 i
. We thus know explicitly λ i since it is equal to α i ∈ C. Likewise, by considering e i + e j , we recover λ ij explicitly.

We want to compute θ B k (0) k∈Z(n) projectively. From equation [START_REF] Boneh | Short signatures from the Weil pairing[END_REF] with

i 1 = k, i 2 = • • • = i r = 0 and X = 0 we get: (6) θ B k (0)θ B 0 (0) . . . θ B 0 (0) = t1,...,tr∈K (t1,...,tr)F =(0,...,0) θ A j1 (t 1 ) . . . θ A jr (t r ), where j = (k, 0, . . . , 0)F -1 ∈ Z(n) (since is prime to n, F is bijective on Z(n)).
For the rest of the discussion, we will suppose that θ B 0 (0) = 0, so if we know how to compute the right hand term, we can recover the theta null point of B up to a non zero projective factor. Of course if this is not the case, we just need to apply Equation ( 5) with i 2 = • • • = i r equal to a non zero coordinate. As we have seen, we can compute exactly the monomials in the sum of the right hand term up to the unknown factors λ i and λ ij . But the following lemma shows that the monomials appearing only depend on these factors to the power of , which we know. Lemma 4.2. Let (t 1 , . . . , t r ) ∈ K r such that (t 1 , . . . , t r )F = (0, 0, . . . , 0) and let (j 1 , . . . , j r ) ∈ Z(n) r such that (j 1 , . . . , j r )F = (k, 0, . . . , 0). Then when we write the product θ A j1 (t 1 ) . . . θ A jr (t r ) in terms of the λ i , λ ij seen as indeterminates, it lies in

C[λ i , λ ij ].
Proof. We want to show that a monomial θ A j1 (t 1 ) . . . θ A jr (t r ) is invariant under any transformation T of C[λ i , λ ij ] that acts on the generators by a th-root of unity.

Fix i 0 ∈ Z(n). We first show that the expression is invariant under the transformation

T of C[λ i , λ ij ] such that T (λ i0 ) = ζλ i0 , T (λ i0j ) = ζλ i0j
where ζ is a th-root of unity, j = i 0 , and T leaves invariant the other generators. We let u = [ ] ((t 1 ) i0 , (t 2 ) i0 , . . . , (t r ) i0 ) . Here, we see t i ∈ K as an element of 1 Z g /Z g that we identify to Z g / Z g via the map [ ] : x → .x. We then have

T (θ A j1 (t 1 ) . . . θ A jr (t r )) = ζ (u 2 1 +...+u 2 r ) θ A j1 (t 1 ) . . . θ A jr (t r
). But we have (t 1 , . . . , t r )F = 0 ∈ K so we are reduced to the following problem: show that for an element u in (Z/ Z) r such that uF = 0, we have u

• t u = 0. But since uF = 0, u is of the form u t F , so u • t u = u • t F • F • t u = u • t u = 0.
Now we fix i 0 , j 0 ∈ Z(n) and we consider the transformation T such that T (λ i0,j0 ) = ζλ i0,j0 and T leaves invariant the other generators. Let

u = [ ] ((t 1 ) i0 , (t 2 ) i0 , . . . , (t r ) i0 ) , v = [ ] ((t 1 ) j0 , (t 2 ) j0 , . . . , (t r ) j0 ) .
We then compute:

T (θ A j1 (t 1 ) . . . θ A jr (t r )) = ζ t u•v θ A j1 (t 1 ) . . . θ A jr (t r
). But since (t 1 , . . . , t r )F = 0, we have uF = vF = 0, and so t uv = t u t F F v = 0 (where u and v are some elements of (Z/ Z) r ).

The transformations T we have considered generate all the transformations we are looking at, this concludes the proof. Now this gives us an algorithm to compute θ B k (0) k∈Z(n) (projectively), since we may take any th-root of the λ i , λ ij , and apply Equation [START_REF] Bröker | Explicit CM-theory in dimension[END_REF]. In fact, Lemma 4.2 states that we get the correct result even if we make the wrong choice. Actually, we do not need to take any th-root, we just need to work symbolically over the ring

C[λ i , λ ij ]/{λ i = α i , λ ij = α ij }.
For the convenience of the reader we give a complete algorithm for g = 2, the advantage of this case being that we need only differential additions, not extended differentials. We leave to the reader the complete algorithm for g > 2 using extended differential additions.

Algorithm 4.3. Input:

The basis e 1 , e 2 given in theta coordinates of a maximal isotropic subgroup K ⊂ A[ ], a complex abelian variety of dimension 2. Output: The theta null point of B = A/K.

• Fix an integer matrix F of rank r such that t F F = Id.

• Compute e 1 + e 2 in A.

• Write the affine theta coordinates of ẽ1 , ẽ2 and ẽ1 + ẽ2 up to the unknown projective factors λ 1 , λ 2 and λ 1,2 that we see as indeterminates. • Use differential additions to compute the affine theta coordinates of all points of

K = 1 Z g /Z g in C[λ 1 , λ 2 , λ 1,2 ].
• From the affine coordinates of ẽ1 and ( + 1)ẽ 1 (where = 2 + 1), recover a relation

λ 1 = α 1 . Likewise, recover relations λ 2 = α 2 and λ 1,2 = α 1,2 . • For all k ∈ Z(n), let j = (k, 0, . . . , 0) F -1 and compute θ B k (0)θ B 0 (0) . . . θ B 0 (0) = t1,.
..,tr∈K (t1,...,tr)F =(0,...,0)

θ A j1 (t 1 ) . . . θ A jr (t r ), in the ring C[λ 1 , λ 2 , λ 1,2 ]/{λ 1 = α 1 , λ 2 = α 2 , λ 1,2 = α 1,2 }. By Lemma 4.2
this is actually an element of C.

4.2.

Computing the image of a point. Now we explain how to compute f (x) from a point x ∈ A. Actually, we fix once and for all z ∈ C g an affine lift of x and explain how to compute (

θ B i ( z)) i∈Z(n) (projectively). Let Y = ( z, 0, . . . , 0) and X = Y F -1 (so that X 1 , . . . , X r are integral multiples of z), let k ∈ Z(n) and j = (k, 0, . . . , 0)F -1 . Proposition 4.1 gives (7) θ B k ( z)θ B 0 (0) . . . θ B 0 (0) = t1,...,tr∈K (t1,...,tr)F =(0,...,0) θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r ).
It remains to explain how to compute the θ A jα (X α + t α ). As with the preceding case, we will only compute them up to unknown projective factors, and then find enough relations on these factors to be able to compute the product θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r ). As before, we let (ẽ i ) i∈ [1,g] be the canonical basis of 1 Z g , and (e 1 , . . . , e g ) the reduced basis on K.

First, we compute x + e i using normal additions. This means that we recover the affine theta coordinates of z + ẽi up to an unknown projective factor µ i . Then we can use differential additions (or extended differential additions) to recover the theta coordinates of z + n 1 ẽ1 + • • • + n g ẽg in terms of the µ i for any n 1 , . . . , n g ∈ Z.

Moreover we know that

θ A k (z + ẽi ) k∈Z(n) = θ A k (z) k∈Z(n) ,
so we can recover from it a relation of the form µ i λ

( -1) i = β i for i ∈ [1, g].
(Remember that we know ẽi only up to the projective factor λ i .) But since we know the value λ i = α i , we thus recover an equation of the form µ i = β i where β i is in C. Now X is of the form (a 11 z, a 12 z, . . . , a 1r z) if (a ij ) i,j∈ [1,r] are the coefficients of the matrix F -1 . By using differential additions we can then recover the theta coordinates of the point

X i + n 1 ẽ1 + • • • + n g ẽg for i ∈ [1, g] up to the unknown {µ i , λ i , λ ij i, j ∈ [1, g], i = j}.
But as in the preceding case, the relations we know on the µ i , λ i and λ ij are sufficient for our purpose: Lemma 4.4. Let (t 1 , . . . , t r ) ∈ K r such that (t 1 , . . . , t r )F = (0, 0, . . . , 0) and let (j 1 , . . . , j r ) ∈ Z(n) r such that (j 1 , . . . , j r )F = (k, 0, . . . , 0). Note X = ( z, 0, . . . , 0)F -1 .

Then, when we write the product θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r ) in terms of the µ i , λ i and λ ij seen as indeterminates, it lies in

C[µ i , λ i , λ ij ].
Proof. Let i 0 ∈ Z(n) and T be the transformation of C[µ i , λ i , λ ij ] such that T (µ i0 ) = ζµ i0 (where ζ is a th-root of unity) and T leaves invariant the other generators. We let u = [ ] ((t 1 ) i0 , (t 2 ) i0 , . . . , (t r ) i0 ) , (m 1 , . . . , m r ) = ( , 0, . . . , 0)F -1 .

We then have

T (θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r )) = ζ (m1u1+...+mrur) θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r
). Since we have mF = uF = 0 in (Z/ Z) r , we know (see the proof of Lemma 4.2) that m • t t = 0. Now we let T be the transformation of C[µ i , λ i , λ ij ] such that T (λ i0 ) = ζλ i0 and T leaves invariant the other generators. With the notations from the last paragraph, we then have

T (θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r )) = ζ u 2 1 +...+u 2 r ζ m1u1+...+mrur θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r ).
We have already seen that the numerator ζ u 2 1 +...+u 2 r and the denominator ζ m1u1+...+mrur are equals to one.

Finally, we fix i 0 and j 0 = i 0 in Z(n) and let T be the transformation thus that T (λ i0,j0 ) = ζλ i0,j0 and T leaves invariant the other generators. Let

u = [ ] ((t 1 ) i0 , (t 2 ) i0 , . . . , (t r ) i0 ) , v = [ ] ((t 1 ) j0 , (t 2 ) j0 , . . . , (t r ) j0 ) .
We compute:

T (θ A j1 (X 1 + t 1 ) . . . θ A jr (X r + t r )) = ζ t u•v θ A j1 (X 1 + t 1 )
. . . θ A jr (X r + t r ); and we have already treated this case in the proof of Lemma 4.2.

Another small technical detail is that in the algebraic setting, we can't fix a lift z ∈ C g . The best we can do is choose an affine point x such that θ i (x) = µ 0 θ i (z). But we have just seen that for an affine lift z, we get a correct result. Since there are infinitely many such affine lift, corresponding to infinitely many µ 0 , and the corrective factors are polynomials in µ 0 , the result is correct for any affine lift.

Once again, we give the full algorithm for g = 2.

Algorithm 4.5. Input:

The basis e 1 , e 2 given in theta coordinates of a maximal isotropic subgroup K ⊂ A[ ], a complex abelian variety of dimension 2, and a geometric point x of A. Output: The point f (x) where f is the isogeny A → A/K.

• Fix an integer matrix F of rank r such that t F F = Id.

• Compute x + e 1 and x + e 2 in A.

• Write the affine theta coordinates of z + ẽ1 , z + ẽ2 up to the unknown projective factors µ 1 , µ 2 that we see as indeterminates (here z is any affine lift of x).

• Use (extended) differential additions to compute the affine theta coordinates of the points

z + t for t ∈ K = 1 Z g /Z g in C[µ 1 , µ 2 , λ 1 , λ 2 , λ 1,2 ]
. Use differential additions again to compute the points m i z + t for i = 1, . . . , r where (m 1 , . . . , m r ) are equal to ( , 0, . . . , 0)F -1 .

• From the affine coordinates of z + ẽ1 and z recover a relation

µ 1 = β 1 .
Likewise, recover a relation µ 2 = β 2 . • For all k ∈ Z(n), let j = (k, 0, . . . , 0) F -1 and compute

θ B k ( x)θ B 0 (0) . . . θ B 0 (0) = t1,.
..,tr∈K (t1,...,tr)F =(0,...,0) Lemma 4.4 this is actually an element of C.

θ A j1 ( m 1 z + t 1 ) . . . θ A jr (m r z + t r ), in the ring C[µ 1 , µ 2 , λ 1 , λ 2 , λ 1,2 ]/{µ 1 = β 1 , µ 2 = β 2 , λ 1 = α 1 , λ 2 = α 2 , λ 1,2 = α 1,2 }. By

Complexity. Our algorithms depends on many parameters:

• the dimension g of the abelian variety,

• the field k where it is defined,

• the degree of the isogeny,

• the level n of the theta structure. The dimension g will be fixed and we assume that n is fixed (remember that in practice we use n = 2 or n = 4). We thus look at the complexity in (and k).

For Algorithms 4.3 and 4.5, the first important step is the computation of O( g ) points using differential additions (or extended differential additions). For computing the theta null point we need all the points in the kernel, so g points, and for computing the image of a point we need r g points. Let k be the field where the geometric points of the kernel (and also the point we want to send) are defined. Then the scalars α i and β i from above live in k . Since the number of coordinates, n g , is fixed we need O( g ) operations in k . (Actually we work over the algebra k [λ i , λ ij , µ i ], but by homogeneity of the addition law we only deal with monomials, so we just need to update the powers in the λ i ).

Next for changing level using Proposition 4.1, the cost is O( rg/2 ) operations in k . Indeed the space of points (t 1 , . . . , t r ) ∈ K r such that (t 1 , . . . , t r )F = 0 is an Z/lZ-vector space of dimension rg/2, so we sum over O( rg/2 ) terms. For each such tuple, we have to reduce the corresponding monomial in the λ i and µ i modulo the relations λ i = α i , µ i = β i . But the highest power appearing in λ i or µ i is r 2 , so we just need to precompute the powers α i , α 2 i , . . . , α r i . With this precomputation, for each term we then do at most (g + g(g + 1)/2) + (r -1) multiplications. Since r = 2 or r = 4, this gives the complexity O( rg/2 ) appearing in Theorem 1.1.

4.4.

The case of level 2. Here we assume that the embedding given by the theta functions of level 2 is projectively normal (in particular the abelian variety is simple), so that the even theta null coordinates are non zero.

We can of course still use Proposition 4.1 in this case, so we just need to explain how we can compute the points

n 1 ẽ1 + . . . n g ẽg ∈ K A = A/ ± 1
starting from the points ẽ1 , . . . , ẽg ∈ K A . In fact, since we can still do differential additions, the only difficulty is to compute the points ẽi + ẽj . By the discussion from Section 3, we can compute {ẽ i ± ẽj } ⊂ K A , but we need to make compatible choices. Fix an element in each of the sets {ẽ 1 ± ẽi }. Then we choose the other elements in {ẽ i ± ẽj } by doing "compatible additions", as described in [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF]Section 3.2.1].

For pushing a point x via the isogeny, likewise we make a choice for the set {x ± e 1 }, and we make choice for the other sets {x ± e i } compatible with the choice for x ± e 1 and the choice e 1 ± e i .

Application to genus 2 curves

In this section, we apply the preceding results in the case where the abelian variety is the Jacobian of an hyperelliptic curve C of genus 2. To compute the isogenous curve we procede as follows: We want to compute an -isogeny between Jac(C) and Jac(C ) where the points are represented by their Mumford's polynomials. We compute the following commutative diagram where points on the abelian varieties A and B are given by theta functions of level n. Remember that for arithmetic reasons we use n = 4 or n = 2 if we work on the Kummer variety.

A k B k thetas of level n Jac k (C) Jac k (C ) Mumford's coordinates
In Section 5.4, we insist on the rationality of the process. Finally, we look at the complexity of computing isogenies in Section 5.5 and give an exemple of computation.

These sections heavily use the following formulae which link the thetas of level 2 with the squares of the thetas of level [START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF][START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF]

: for all a, b ∈ 1 2 Z 2 /Z 2 , 4Θ [ a b ] (z, Ω) 2 = β∈ 1 2 Z 2 /Z 2 (-1) 4 t aβ Θ 0 b+β z, Ω 2 Θ 0 β 0, Ω 2 Θ [ 0 b ] z, Ω 2 Θ [ 0 0 ] 0, Ω 2 = α∈ 1 2 Z 2 /Z 2 Θ [ α b ] (z, Ω) 2
Note that the theta functions of level (2, 2) are evaluated at z and not at 2z.

To have compact formulae we number the theta functions of level 4 as given in the appendix (we follow Dupont [START_REF] Dupont | Moyenne arithmético-géométrique, suites de Borchardt et applications[END_REF]). Moreover, for the theta constants, we omit the argument 0 and write Θ i instead of Θ i (0).

Computing theta constants from the equation of the curve.

Let C be an hyperelliptic curve of genus 2 given by the equation y 2 = f (x) over C. Thomae's formulae [START_REF] Mumford | Tata lectures on theta II[END_REF]III.8] give relations between the roots of f and the fourth power of the theta constants of level (2, 2) with period matrix Ω associated to C.

For instance, assumes that the curve is in Rosenhaim form

y 2 = x(x -1)(x -λ)(x -µ)(x -ν)
then the ordering {0, 1, λ, µ, ν} leads to the following relations:

Θ4 Θ0 4 = µ λν Θ8 Θ0 4 = µ(ν-1)(λ-µ)µ ν(µ-1)(λ-ν) Θ1 Θ0 4 = µ(ν-1)(λ-1)
λν(µ-1)

Θ2 Θ0 4 = µ(λ-1)(ν-µ) λ(µ-1)(ν-λ)
We keep this choice for the rest of the paper. Note that another choice of ordering leads to an isomorphic variety (over C). In previous work [START_REF] Gaudry | Fast genus 2 arithmetic based on theta functions[END_REF] the ordering {ν, µ, λ, 1, 0} was used but this choice implies the use of √ -1 which is not the case with our ordering.

To get the equations defining the abelian variety A, we need to know how to take the roots in Thomae's formulae. Of course this is easy if we are in a subfield of C since we can evaluate the theta constants. However, this cannot be done in finite fields.

Since we are only interested in finding an abelian variety A k (given by theta constants of level n) isomorphic to the Jacobian of the curve, we can choose A k up to isomorphism.

A matrix γ =

A B C D in the group Sp(4, Z) acts on C 2 × H 2 in the following way

C 2 × H 2 -→ C 2 × H 2 (z, Ω) -→ (γ.z, γ.Ω) = t (CΩ + D) -1 z, (AΩ + B) (CΩ + D) -1
This action defines an isomorphism between the two tori:

C 2 / ΩZ 2 + Z 2 C 2 / γ.ΩZ 2 + Z 2 z → γ.z
On the other hand, each isomorphism between two tori comes from a matrix γ in Sp(4, Z). The only matrix γ ∈ Sp(4, Z) such that γ.Ω = Ω for all Ω ∈ H 2 are the matrices γ = ± Id 4 . The matrix -Id 4 acts on C 2 / ΩZ 2 + Z 2 by the automorphism z → -z and the equation of A is invariant under this automorphism, thus we will identify γ with -γ. We will need the following subgroups of Sp(4, Z):

Γ (n) = Γ (n, n) = {γ ∈ Sp(4, Z), γ ≡ ± Id 4 [n]} Γ (n, 2n) = A B C D ∈ Γ (n), diag t AC ≡ diag t BD ≡ 0 [2n]
Note that Γ (n) corresponds to the group of isomorphisms which fix the n-torsion of the torus modulo the automorphism z → -z. Let's study the action of these groups on the theta constants of level n for n even. Mumford [START_REF] Mumford | Tata lectures on theta I[END_REF] showed that for γ ∈ Γ (1, 2) it is given by

Θ [ 0 0 ] (γ.z, γ.Ω) = Θ [ 0 0 ] (z, Ω)C γ exp πi t (CΩ + D) -1 Cz
where C γ is a complex number which depends only on γ and Ω. for characteristics

(a, b) in 1 n Z 4 /Z 4 and for γ = A B C D in Γ (n) we put z = γ -1 .(Ωa + b) in the preceding equation to obtain Θ [ a b ] (0, γ.Ω) Θ [ 0 0 ] (0, γ.Ω) = Θ [ a b ] (0, Ω) Θ [ 0 0 ] (0, Ω) exp πi t a t DBa -πi t b t ACb -2πi t a(A -Id)b
In fact an element γ not in Γ (n) does not preserve the characteristics of the theta constants in the quotient. Thus Γ (n) is exactly the group of isomorphisms which fix the 2n-th power of the theta constants of level (n, n) (modulo a constant), Γ (n, 2n) the n-th power and Γ (n 2 , 2n 2 ) the theta constants of level (n, n).

The choice of the ordering of the roots of the hyperelliptic polynomial corresponds to the choice of a numbering of the two-torsion, thus of a fixed class in Γ (1)/Γ [START_REF] Birkenhake | Complex abelian varieties, volume 302 of Grundlehren der Mathematischen Wissenschaften[END_REF]. With the possible use of an element of Γ (2)/Γ (2, 4) we can take the square roots of the following quotients in an arbitrary way:

Θ 1 Θ 0 4 , Θ 2 Θ 0 4 , Θ 4 Θ 0 4 , Θ 8 Θ 0 4 .
The other squares of theta constants of level (2, 2) are given by the formulae:

Θ 2 6 = 1 ν Θ 2 0 Θ 2 2 Θ 2 4 Θ 2 12 = 1 λ Θ 2 0 Θ 2 8 Θ 2 4 Θ 2 3 = (ν -1) Θ 2 4 Θ 2 6 Θ 2 1 Θ 2 9 = (λ -1) Θ 2 4 Θ 2 12 Θ 2 1 Θ 2 15 = Θ 2 0 Θ 2 3 -Θ 2 1 Θ 2 2 Θ 2 12 . For each quotient Θ [ a b ] 2 /Θ [ 0 0 ] 2 with a, b in ( 1 2 Z 2 )/Z 2 ,
there exists an element of Γ (2, 4)/Γ (4, 8) witch changes its sign but leaves invariant the other quotients (Note that this works because some theta constants are zero). Therefore to get the variety A in level 4 we can take arbitrary square roots of each quotient.

Computing the equation of the curve from theta constants.

From the squares of the theta constants of level (2, 2), the underlying hyperelliptic curve is given by the equation

y 2 = x(x -1)(x -λ)(x -µ)(x -ν) with λ = Θ 2 0 Θ 2 8 Θ 2 4 Θ 2 12 , µ = Θ 2 8 Θ 2 2 Θ 2 12 Θ 2 6 , ν = Θ 2 2 Θ 2 0 Θ 2 6 Θ 2 4 .

Maps between abelian varieties and Jacobians.

We need to link divisors in the Jacobian of the curve (given by their Mumford's coordinates) and points on the abelian variety given by theta functions of level n. The formulae are given in the appendix. They come from Mumford [START_REF] Mumford | Tata lectures on theta II[END_REF] and Van Wamelen [START_REF] Van Wamelen | Equations for the Jacobian of a hyperelliptic curve[END_REF].

Of course, it is not possible to compute v from the theta of level 2. In fact only its square is computable. This is coherent with the fact that level 2 corresponds to the Kummer variety.

For the level n = 4, we still have to find the value of c 1,2 √ a 2 -a 1 in the formulae of the appendix. With our numbering of the roots of the hyperelliptic polynomial, √ a 2 -a 1 = √ 1 -0 can be chosen to be 1. The constant c 1,2 is just a sign and corresponds to the action of the automorphism P → -P in the abelian variety.

Thus it can be chosen arbitrary. Over C the choice of this sign corresponds to the choice of the orientation of the paths used to compute the Abel-Jacobi map. 5.4. Rationality considerations. Although the process of computing isogenies can be made rational, our algorithms clearly use arithmetic in fields extension. The first extension comes from the fact that an abelian variety of level n associated to a given curve cannot be defined on the same field as the curve. If the base field is k, we will denote k the extension where the theta null point of level n lives. Then if P is a rational point on the Jacobian, its theta coordinates will live in k . If the curve is defined over a finite field then the arithmetic must be performed in an extension field of degree at most 2 if n = 2 or 4 if n = 4. This requires to find quadratic non-residues.

In particular, if one is interested in computing all the isogenous curves, he must compute the possible kernels of the isogeny as a rational subgroup of Jac(C) and not as rational subgroup of A (where we can only look at k -rational isogenies). Thus for computing chains of isogenies, one must always return to the curves in Weierstrass form for the isogenies to be rational.

The second extension comes from the fact that for the isogeny algorithm we work over the field of definition of the theta coordinates of the points of the kernel. If the points live in an extension k of k, then by the above discussion, their theta coordinates will live in the composite extension of k and k over k. Since the result of the isogeny computation of Section 4 give elements of k , it should be possible to not take this extension by decomposing the right side member of ( 5) as elementary symmetric functions on the points of the kernel.. With our method, we compute the Rosenhain invariants of the isogenous curves. Hence, as remarked above, its equation may not be on the same base field as the original curve. To avoids this we can compute its absolute invariants which are elements of the base field since the isogenous curve is defined over the same field as the curve. With Mestre's algorithm [START_REF] Mestre | Construction de courbes de genre 2 à partir de leurs modules[END_REF], an equation over the base field can be found. It remains to find an isomorphism between the two equations and to push the points.

In the case where the two-torsion is rational on the first curve, the two-torsion will be rational on the isogenous curve (the degree of the isogeny being odd). Thus the isogenous curve admits an equation in Rosenhain form over the base field. In this case we don't need Mestre's algorithm since our algorithm returns the correct curve. 5.5. Complexity. Let C be an hyperelliptic curve of genus 2 over a field k. Assume that we are given a rational isotropic subgroup K of the -torsion defined by two generators in Mumford coordinates (possibly over an extension field). The cost of computing the abelian variety A of level n associated to C and of sending the two generators of K and their sum can be done in O [START_REF] Atkin | The number of points on an elliptic curve modulo a prime[END_REF]. Computing the abelian variety B = A/K is O( r ) operations in the composite field k 0 of the field of definition k of the geometric points of K and k (notations as in the Section 5.4). Finally the reconstruction of the isogenous curve is O [START_REF] Atkin | The number of points on an elliptic curve modulo a prime[END_REF].

However, k is the field of definition of the theta null point of level n of A. Since the theta null point is rational when the 2n-torsion is, the degree of this extension is bounded by a function of n. For instance, over a finite field it is bounded by (2n) 2g .

Since n (and g) are fixed, this means that computing B/K can be done in O( r ) operations in k .

For sending a point between two Jacobians, the cost of the morphisms is also a O(1) while the cost of pushing the point between A and B is O( r ) operations in k 0 (and thus in k ).

Lastly, if C is defined over a finite field k and K is rational, then the field k where the geometric points of K are defined lie in an extension of degree at most 2 -1 of k. This concludes the proof of Theorem 1.2. (We can even bound the extension degree by -1 when is splits completely in the endomorphism ring of the Jacobian).

5.6. Implementations. Together with Gaetan Bisson we have implemented the computation of -isogenies in a Magma package called AVIsogenies (it can be found at http://avisogenies.gforge.inria.fr/). To have an efficient implementation we designed some specific codes for genus 2 and level 2. In particular, it avoids taking some of the field extensions.

For instance, take the hyperelliptic curve:

y 2 = x 5 + 41691x 4 + 24583x 3 + 2509x 2 + 15574x
over the finite field F 42179 . The cardinality of the Jacobian is 2 10 1321 2 and there is one rational isotropic subgroup K of = 1321 torsion. The isogenous curve with respect to K is

y 2 = 33266x 6 + 20155x 5 + 31203x 4 + 9732x 3 + 4204x 2 + 18026x + 29732
The computation took around two hours on a core 2 with 32 GB of RAM. This exemple was specifically chosen so that the theta null point of level 2 is rational over the base field, and also all the geometric points in the kernel. Thus we avoided some intermediate field extensions. Taking a field extension would increase the computation by a quadratic or linear factor (depending on whether asymptotically fast algorithms are used for the arithmetic).

Even if the morphisms are O(1) in theory, we saw that in practice their computations are not negligible. This is especially the case when is small: most of the time is spend by converting points from Mumford's coordinates to theta coordinates.

Conclusion

In Section 4, we have explained how to compute isogenies between abelian varieties described by theta coordinates of level n. In fact, the algorithms from this section can be seen as a composition from the algorithms of [START_REF] Lubicz | Computing isogenies between abelian varieties[END_REF], which describe the isogeny with theta functions of level n on the domain, and theta functions of level n on the codomain, and an algorithm to convert from level n theta functions to level n theta functions induced by Koizumi's addition formulae. The techniques developed in this paper also allow to convert from level n theta coordinates to level n theta coordinates (provided that we know the level n coordinates of the points of -torsion), thus an easy adaptation of Algorithm 4.3 gives a method to convert between theta functions of different level. More details on this method can be found in [START_REF] Robert | Theta functions and applications in cryptography[END_REF]Section 7.8].

One drawback of Theorems 1.1 and 1.2 is that they apply only to maximal isotropic kernels. When we look at isogenies graphs in genus 2 for instance, we do not always recover the full isogenies graphs by only looking at ( , )-isogenies.

It would be interesting to relax this condition of maximality, and in particular to obtain an algorithm to compute an isogeny with a cyclic kernel. The major difficulty of looking at isogenies whose kernel is not maximally isotropic is that the pullback of the polarisation by this isogeny is much harder to describe algebraically.

(z, Ω) , Θ 15 (z) = Θ ( 1 2 1 2 ) ( 1 2 1 2 ) (z, Ω) .
A.2. Notations. In this section we recall some notations of Van Wamelen [START_REF] Van Wamelen | Equations for the Jacobian of a hyperelliptic curve[END_REF] which we apply in the genus 2 case. Assume that the roots of f (which is of degree 5) are numbered: {a 1 , . . . , a 5 }. Let

η 1 = 1 2 , 0; 0, 0 η 2 = 1 2 , 0; 1 2 , 0 η 3 = 0, 1 2 ; 1 2 , 0 η 4 = 0, 1 2 ; 1 2 , 1 2 η 5 = 0, 0; 1 2 , 1 2 η ∞ = [0, 0; 0, 0]
For a subset S in {1, . . . , 5, ∞}, we set

η S = i∈S η i
We define η S and η S to be the first and second part of η S . This notation comes from the fact that the divisor i∈S a i -#S(∞) is mapped to Ωη S + η S by the Abel-Jacobi map.

All theta functions of level (2, 2) can be written as Θ [η U oA ] with U = {1, 3, 5} and a subset A of {1, . . . , 5} of odd cardinality where o denote the symmetric difference of two sets. For each such subset, Van Wamelen defines (definition 3) the function t A (z) to be t

A (z) = f A Θ [η U oA ] (z) where f A is a constant which is f A = Θ [0] /Θ [η U oA ]
for the even functions (i.e. #A = 3) and for the others

f 1 = -1 √ a2-a1 Θ0Θ4Θ6Θ12 Θ1Θ3Θ9Θ15 f 2 = -1 √ a2-a1 Θ4Θ6Θ12 Θ2Θ8Θ15 f 3 = -1 √ a2-a1 Θ0Θ6 Θ2Θ3 f 4 = 1 √ a2-a1 Θ4 Θ1 f 5 = -1 √ a2-a1 Θ0Θ12 Θ8Θ9 f {1,2,3,4,5} = f ∅ = -1 √ a2-a1 3 Θ 2 4 Θ 2 6 Θ 2 12

Θ1Θ2Θ3Θ8Θ9Θ15

Note that we made a choice of the sign of the last six f A . If A is not of even cardinality, we write t A and f A instead of t A c and f A c where A c denotes the complement set of A in {1, . . . , 5}. We have the following Theorem: Theorem A.1. Let D = P 1 + P 2 -2(∞) be a non theta divisor which corresponds to a vector z ∈ C 2 /(ΩZ 2 + Z 2 ). Let (x i , y i ) be the coordinates of the point P i . Write (u, v) for the Mumford's polynomials of D. For k ∈ {1, . . . , 5}, and l, m two distinct elements of {1, . . . , 5} \ {k} we have In particular, in genus 2, if the divisor is not of two torsion then not two odd theta functions are zero.

U (a k ) = t 2 k (z) t 2 ∅ (z) , V (a k ) = Y k,m -Y k,l a l -a m , Y l,m := y 1 (x 2 -a l )(x 2 -a m ) -y 2 (x 1 -a l )(x 1 -a m ) x 2 -x 1 = c 1,
A.3. From theta to Mumford. Let C be the hyperelliptic curve y 2 = f (x). Write a i for the roots of f with a choice of an ordering. Assume that the divisor D in Jac(C) \ Θ is given by the mean of theta functions of level n with n = 2 or n = 4.

The following formulae allow to compute u, v by using Lagrange interpolation.

u(a 1 ) = (a 2 -a 1 ) A.4. From Mumford to Theta. Let D = g i=1 P i -gP ∞ be a divisor in Jac(C) corresponding to z ∈ C 2 /(ΩZ 2 + Z 2 ). Assume that D is given by its Mumford's coordinates (u, v) (or u and v 2 if we work on the Kummer surface). As before, we assume here that the divisor is generic. Note that we work with projective coordinates so we only want the theta functions of level n up to a constant factor (which will be 1/Θ 14 (z) for n = 2 and 1/Θ 14 (z) 4 for n = 4).

From v 2 it is possible to compute the squares of the Y i,j since the formulae defining Y 2 i,j can be made algebraic in terms of the coefficient of u and v 2 . By evaluating u at the root of f , we obtain formulae for all the Θ i (z) 2 /Θ 14 (z) 2 with 0 ≤ i ≤ 15. If we want the theta of level 2 we are done.

For level n = 4, we can invert the previous formulae and use the Frobenius relations. A more natural way is to use the doubling formulae [START_REF] Gaudry | Fast genus 2 arithmetic based on theta functions[END_REF]:

4Θ [ a b ] (2z) Θ [ a b ] Θ [ 0 0 ] 2 = α,β∈ 1 2 Z 2 /Z 2 exp -4iπ t aβ Θ a+α b+β (z) 2 Θ [ α β ] (z) 2 4Θ [ a b ] (2z) Θ [ a 0 ] Θ [ 0 b ] Θ [ 0 0 ] = α,β∈ 1 2 Z 2 /Z 2 exp -4iπ t aβ Θ a+α b+β (z) Θ a+α β (z) Θ [ α b+β ] (z) Θ [ α β ] (z) .
The first formula allows to recover the even theta functions. For the odd theta functions, we will use the second formula. The products on the right side can be expressed in terms of the constants f A and the functions Y l,m , Y and u(a i ). Since we need to divide by some u(a i ), we make the hypothesis that the divisor is not of 2-torsion. We only worked in the generic case but the formulae can be extended to degenerate divisors: see for instance Gaudry [START_REF] Gaudry | Fast genus 2 arithmetic based on theta functions[END_REF] for level n = 2.

Algorithm 5 . 1 .

 51 Input: A genus 2 curve C over a field k, a maximal isotropic subgroup K of Jac(C)[ ]. Output: A curve C over k such that Jac(C ) = Jac(C)/K.• Find a basis of K in Mumford's coordinates. • Find a Rosenhain equation of the curve C. • Use Thomae's formulae to compute the 4th power of theta constants of level n of the corresponding abelian variety A k (Section 5.1). • Extract the roots to get the theta constants (Section 5.1). • Send the basis of K in A k (Section 5.3 and the appendix). • Apply algorithms 4.3 and 4.5 to get the theta constants of the isogenous abelian variety B k . • Recover a Rosenhain form of C (Section 5.2). • If needed, apply Mestre's algorithm to recover a rational equation of C .

  This is Theorems 4, 5, 6 and 7 of Van Wamelen. By using a similar argument as in the proof of Theorem 6 for Y l,m Y l,k instead of Y 2 l,m , we can compute the products c l,m c l,k (where c i,j are the signs in Wamelen's theorems) in terms of theta constants. With our choice of constants f A , we find that c i,j = c 1,2 . With (almost) the same proof as Van Wamelen we haveTheorem A.2. With the previous notations and choices,Y := y 1 y 2 = 5 l=1 t l (z) t ∅ (z)Non generic divisors D can easily be recognized in Mumford's coordinates (u, v). Let z be the image of D by the Abel-Jacobi map. Let Θ be the set of all theta divisors in the Jacobian,D ∈ Θ ⇐⇒ deg(u) ≤ 1 ⇐⇒ t ∅ (z) = 0 ⇐⇒ Θ 14 (z) = 0. D ∈ Θ + (a k -(∞)) ⇐⇒ u(a k ) = 0 ⇐⇒ t k (z) = 0 ⇐⇒ Θ η U •{k} (z) = 0.

  Applying the previous theorem, we have whereA = a 2 + b 2 + c 2 + d 2 , B = a 2 + b 2 -c 2 -d 2 , C = a 2 -b 2 + c 2 -d 2 , D = a 2 -b 2 -c 2 + d 2 , E = A B C D (a 2 d 2 -b 2 c 2 )(a 2 c 2 -b 2 d 2 )(a 2 b 2 -c 2 d 2 ) , F = (a 4 -b 4 -c 4 + d 4 )/(a 2 d 2 -b 2 c 2 ), G = (a 4 -b 4 + c 4 -d 4 )/(a 2 c 2 -b 2 d 2 ), H = (a 4 + b 4 -c 4 -d 4 )/(a 2 b 2 -c 2 d 2 ).

  2 t l (z)t m (z)t {l,m} (z) t 3 ∅ (z) where c 1,2 is just a sign ±1.

  For instance,Θ 14 (2z)Θ 0 Θ 2 Θ 12 = Θ 0 (z)Θ 2 (z)Θ 12 (z)Θ 14 (z) -Θ 5 (z)Θ 7 (z)Θ 9 (z)Θ 11 (z) +Θ 4 (z)Θ 6 (z)Θ 8 (z)Θ 10 (z) -Θ 1 (z)Θ 3 (z)Θ 13 (z)Θ 15 (z) Θ 14 (2z)Θ 0 Θ 2 Θ 12 = t 2,4 (z)t 2,3 (z)t 3,4 (z)t ∅ (z) f 2,4 f 2,3 f 3,4 f ∅ + t 1,5 (z)t 2 (z)t 4 (z)t 3 (z) f 1,5 f 2 f 4 f 3 + t 3,5 (z)t 4,5 (z)t 2,5 (z)t 1 (z) f 3,5 f 4,5 f 2,5 f 1 + t 1,3 (z)t 1,4 (z)t 1,2 (z)t 5 (z) f 1,3 f 1,4 f 1,2 f 5 , Θ 14 (2z)Θ 0 Θ 2 Θ 12 t 4 ∅ (z) = Y 2,4 Y 2,3 Y 3,4 u(a 2 )u(a 3 )u(a 4 ) 1 f 2,4 f 2,3 f 3,4 f ∅ + Y 1,5 Y u(a 1 )u(a 5 ) 1 f 1,5 f 2 f 3 f 4 + Y 2,5 Y 3,5 Y 4,5 Y u(a 2 )u(a 3 )u(a 4 )u(a 5 ) 2 1 f 2,5 f 3,5 f 4,5 f 1 + Y 1,2 Y 1,3 Y 1,4 Y u(a 1 ) 2 u(a 2 )u(a 3 )u(a 4 ) 1 f 1,2 f 1,3 f 1,4 f 5 .

Appendix A. Explicit formulae for the conversion between Mumford and theta coordinates A.1. Numbering.

The products of theta functions involved can be computed from the theta of level 4 by:

From the theta functions of level 2 we can compute the Θ i (z) 2 and thus find the polynomial u. Since we have quotiented the abelian variety by {±1}, we can't recover v but only its square. The formulae for Y 2 1,2 , Y 2 1,3 and Y 2 2,3 involve only squares. It remains to compute the products Y 1,2 Y 1,3 , Y 1,2 Y 2,3 and Y 1,3 Y 2,3 and thus we need the following products of theta functions:

If we write x, y, z, t for Θ 0 (z), Θ 1 (z), Θ 2 (z), Θ