Luca De Feo

Cyril Hugounenq

Jérôme Plût

Éric Schost

Explicit isogenies in quadratic time in any characteristic

Consider two ordinary elliptic curves E, E defined over a finite field Fq, and suppose that there exists an isogeny ψ between E and E . We propose an algorithm that determines ψ from the knowledge of E, E and of its degree r, by using the structure of the -torsion of the curves (where is a prime different from the characteristic p of the base field).

Our approach is inspired by a previous algorithm due to Couveignes, that involved computations using the p-torsion on the curves. The most refined version of that algorithm, due to De Feo, has a complexity of Õ(r 2 )p O(1) base field operations. On the other hand, the cost of our algorithm is Õ(r 2 ) log(q) O(1) , for a large class of inputs; this makes it an interesting alternative for the medium-and large-characteristic cases.

Introduction

Isogenies are non-zero morphisms of elliptic curves, that is, non-constant rational maps preserving the identity element. They are also algebraic group morphisms. Isogeny computations play a central role in the algorithmic theory of elliptic curves. They are notably used to speed up Schoof's point counting algorithm [Sch85,Atk88,Sch95,Elk98]. They are also widely applied in cryptography, where they are used to speed up point multiplication [GLV01, LS14], to perform cryptanalysis [MMT01], and to construct new cryptosystems [Tes06, CLG09, Sto10, DFJP14, JS14].

The degree of an isogeny is its degree as a rational map. If an isogeny has degree r, we call it an r-isogeny, and we say that two elliptic curves are r-isogenous if there exists an r-isogeny relating them. Accordingly, we say that two field elements j and j are r-isogenous if there exist r-isogenous elliptic curves E and E such that j(E) = j and j(E ) = j . The explicit isogeny problem has many incarnations. In this paper, we are interested in the variant defined below.

Explicit isogeny problem. Given two j-invariants j and j , and a positive integer r, determine if they are r-isogenous. In that case, compute curves E, E with j(E) = j and j(E ) = j , and the rational functions defining an r-isogeny ψ : E → E .

A good measure of the computational difficulty of the problem is given by the isogeny degree r. Indeed the output is represented by O(r) base field elements, hence an asymptotically optimal algorithm would solve the problem using O(r) field operations. Even though the input size is logarithmic in r, by a slight abuse we say that an algorithm solves the isogeny problem in polynomial time if it does so in the size of the output. Thanks to Vélu's formulas [Vél71], in particular the version appearing in [Koh96,§2.4], we can compute ψ from the knowledge of the polynomial h vanishing on the abscissas of the points in ker ψ, at the cost of a constant number of multiplications of polynomials of degree O(r). Given that all known algorithms to compute h require more than a few polynomial multiplications, we often say that we have computed ψ whenever we have computed h, and conversely.

2000 Mathematics Subject Classification 11Y40 (primary), 11G20, 14H52 (secondary).

This work was partially supported by the DIGITEO grant 2013-0531D (ARGC) and NSERC.

This paper focuses on the explicit isogeny problem for ordinary elliptic curves over finite fields. A famous theorem by Tate [Tat66] states that two curves are isogenous over a finite field if and only if they have the same cardinality over that field. The explicit isogeny problem stated here appears naturally in the Schoof-Elkies-Atkin point counting algorithm (SEA). There, E is a curve over F q , whose rational points we wish to count, and E is an r-isogenous curve, with r a prime of size approximately log(q). For this reason, the explicit isogeny problem is customarily solved without prior knowledge of the cardinality of E(F q ). We abide by this convention here.

Many algorithms have been suggested over the years to solve the explicit isogeny problem. Early algorithms were due to Atkin [Atk91] and Charlap, Coley and Robbins [CCR91].

Elkies ' [Elk98,BMSS08] was the first algorithm targeted to finite fields (of large enough characteristic). Assuming r is prime, its complexity is dominated by the computation of the modular polynomial Φ r , which is an object of bit size O(r 3 log(r)). Later Bröker, Lauter and Sutherland [BLS12] optimized the modular polynomial computation in the context of the SEA algorithm [Sut13b]. Finally Lercier and Sirvent [LS08, LV16] generalized Elkies' algorithm to work in any characteristic. Despite these advances, the overall cost of Elkies' algorithm and its variants is still at least cubic in r.

Another line of work to solve the explicit isogeny problem for ordinary curves was initiated by Couveignes [Cou94,Cou96,Cou00], and later improved by De Feo and Schost [DF11, DFS12]. These algorithms use an interpolation approach combined with ad-hoc constructions for towers of finite fields of characteristic p. Their complexity is quasi-quadratic in r, but exponential in log(p), hence they are only practical for very small characteristic.

In this paper we present a variant of Couveignes' algorithm with complexity polynomial in log(p) and quasi-quadratic in r. Like the original algorithm, it is limited to isogenies of ordinary curves. Together with the Lercier-Sirvent algorithm, they are the only polynomial-time isogeny computation algorithms working in any characteristic, hence they are especially relevant for counting points in medium characteristic (i.e., counting points over F p n , when n p/ log(p)). Note that, although Couveignes-type algorithms do not make use of the modular polynomial Φ r , its computation is still necessary in the context of the SEA algorithm. Thus our new algorithm does not improve the overall complexity of point counting, though it may provide a speed-up in some cases. It gives, however, an effective algorithm for solving the explicit isogeny problem, with potential applications in other contexts, e.g., cryptography.

Notation

Throughout this paper: r is a positive integer, p an odd prime, q a power of p, and F q is the finite field with q elements. E is an ordinary elliptic curve over F q , its group of n-torsion points is denoted by E[n], its q-Frobenius endomorphism by π. The endomorphism ring of E is denoted by O, with K = O ⊗ Q the corresponding number field, O K its maximal order, and d K the discriminant of O K . For a prime different from p and not dividing r, we denote by

E[ k ] the group of k -torsion points of E, E[ ∞ ] = lim -→ E[ k ] the union of all E[ k ], and
T (E) = lim ← - E[ k ] the -adic Tate module [Sil92, III.7],
which is free of rank two over Z . The factorization of the characteristic polynomial of π over Z is determined by the Kronecker symbol (d K / ). If (d K / ) = +1 then we also define λ, µ as the eigenvalues of π in Z and write h = v (λ -µ), where v is the -adic valuation.

We measure all computational complexities in terms of operations in F q ; the boolean costs associated to the algorithms presented next are negligible compared to the algebraic costs, and will be ignored. We use the Landau notation O( ) to express asymptotic complexities, and the notation Õ( ) to neglect (poly)logarithmic factors. We let M(n) be a function such that polynomials in F q [x] of degree less than n can be multiplied using M(n) operations in F q , under the assumptions of [vzGG99,Chapter 8.3]. Using FFT multiplication, one can take

M(n) ∈ O(n log(n) loglog(n)).

Couveignes' algorithm and our contribution

Couveignes' isogeny algorithm takes as input two ordinary j-invariants j, j ∈ F q , and a positive integer r not divisible by p, and returns, if it exists, an r-isogeny ψ : E → E , with j(E) = j and j(E ) = j . It is based on the observation that the isogeny ψ must put E[p k ] in bijection with E [p k ], in a way that is compatible with their structure as cyclic groups. It proceeds in three steps:

(1) Compute generators P, P of E[p k ] and E [p k ] respectively, for k large enough;

(2) Compute the interpolation polynomial L sending x(P ) to x(P ), and the abscissas of their scalar multiples accordingly;

(3) Deduce a rational fraction g(x)/h(x) that coincides with L at all points of E[p k ], and verify that it defines the x-component of an isogeny of degree r. If it does, return it; otherwise, replace P with a scalar multiple of itself and go back to Step (2). For this algorithm to succeed, enough interpolation points are required. Given that the xcomponent of ψ is defined by O(r) coefficients, we have p k ∈ Θ(r). However, most of the time, those points are not going to be defined in the base field F q , so we must use efficient algorithms to construct and compute in towers of extensions of finite fields. Indeed, Couveignes and his successors go at great length in studying the arithmetic of Artin-Schreier towers [Cou00, DFS12], and the adaptation of the fast interpolation algorithm to that setting [DF11]. Using these highly specialized constructions, Steps (1) and (2) are both executed in time Õ(p k+O(1) ) = Õ(rp O(1) ). However the last step only succeeds for one pair of torsion points P, P , in general, thus O(r) trials are expected on average. Hence, the overall complexity of Couveignes' algorithm is Õ(r 2 p O(1) ), i.e., quadratic in r, but exponential in log(p). Although the exponent of p is relatively small, Couveignes algorithm quickly becomes impractical as p grows.

In this paper we introduce a variant of Couveignes' algorithm with the same quadratic complexity in r, and no exponential dependency in log(p).

The bottom line of our algorithm is elementary: replace E[p k ] in the algorithm with E[ k ], for some small prime . However a naive application of this idea fails to yield a quadratic-time algorithm. Indeed, in the worst case one has 2k ∈ Θ(r), with E[ k ] (Z/ k Z) 2 . Hence, two generators P, Q of E[ k ] must be mapped onto two generators of E [ k ]. This can be done in O( 4k ) possible ways, with a best possible cost of O( 2k ) per trial, thus yielding an algorithm of complexity O( 6k ) = O(r 3 ) at best.

To avoid this pitfall, we carefully study in Section 2 the structure of E[ k ], and its relationship with the Frobenius endomorphism π. With that knowledge, we can put some restrictions on the generators P, Q, as explained in Section 3, thus limiting the number of trials to O( 2k ). In Section 4 we present an interpolation algorithm adapted to the setting of -adic towers, and in Section 5 we put all steps together and analyze the full algorithm. Finally in Section 6 we discuss our implementation and the performance of the algorithm.

Towers of finite fields

The algorithms presented next operate on elements defined in finite extensions of F q . Specifically, we will work in a tower of finite fields

F q = F 0 ⊂ F 1 ⊂ • • • ⊂ F n , with dividing #F 1 -1, d 1 = [F 1 : F 0 ] dividing -1,
and [F i+1 : F i ] = for any i > 0. For = 2, we build upon the work of Doliskani and Schost [DS15], whereas for general we use towers of Kummer extensions in a way similar to [DDS13, §2]. Both constructions represent elements of F i as univariate polynomials with coefficients in F q , thus basic arithmetic operations can be performed using modular polynomial arithmetic over F q . While constructing the tower, we also enforce special relations between the generators of each level, so that moving elements up and down the tower, and testing membership, can be done at negligible cost.

We briefly sketch the construction for odd . We first look for a primitive polynomial

P 1 ∈ F q [x] of degree equal to [F 1 : F 0 ].
There are many probabilistic algorithms to compute P 1 in expected time polynomial in and log(q); since their cost does not depend on the height n of the tower, we neglect it (in all that follows, by expected cost of an algorithm, we refer to a Las Vegas algorithm, whose runtime is given in expectation). Then, the image x 1 of x in F 1 = F q [x]/P 1 (x) is an element of multiplicative order #F 1 -1, and in particular it is not a -th power. Hence for any i > 1 we define F i as F q [x]/P 1 x i-1 , the computation of the

polynomials P 1 x i-1
incurring no algebraic cost. Using this representation, elements of F i can be expressed as elements of a higher level F i+j , and reciprocally, by a simple rearrangement of the coefficients. Another fundamental operation can be done much more efficiently than in generic finite fields, as the following generalization of [DS15, §2.3] shows.

Lemma 1.1. Let F 0 ⊂ • • • ⊂ F n be a Kummer tower as defined above, and let a ∈ F i for some 0 i n. For any integer j, we can compute the (#F j )-th power of a using O( i-1 M( )) operations in F q , after a precomputation independent of a of cost O( M( ) log(q)).

Proof. Without loss of generality, we can assume that j < i; otherwise, the output is simply a itself. Let s = #F j , and let d = [F i :

F 1 ] = i-1 . Let x i be the image of x in F i = F q [x]/P i (x), so that x d i = x 1 . The first step, independently of a, is to compute y = x s i . Writing s = ud + r, with r < d, we see that y is given by x u mod #F1 1 x r i . We compute x u mod #F1 1 using O( M( ) log(q)
) operations in F q , and we keep this element as a monomial of

F 1 [x i ].
By assumption, a is represented as a polynomial in x i of degree less than

[F i : F 0 ]. We rewrite it as a = a 0 + a 1 x i + • • • + a d-1 x d-1 i , with a i ∈ F 1 .
This is done by a simple rearrangement of the coefficients of a.

Finally, we compute a(y) by a Horner scheme. All powers y k we need are themselves monomials in F 1 [x i ], each computed from the previous one using O(M( )) operations in F q , for a total of O( i-1 M( )). Finally the monomials a k y k are combined together to form a polynomial in (x 1 , x i ) of degree less than (d 1 , d), and then brought to a canonical form in F i via another rearrangement of coefficients.

Summarizing, the following computations can be performed in a Kummer tower at the indicated asymptotic costs, all expressed in terms of operations in F q .

-basic arithmetic operations (addition, multiplication) in F i , using O(M( i )) operations; -inversion in F i using O(M( i ) log( i )) operations (when = 2, a factor of i can be saved here [DS15], but we will disregard this optimization for simplicity.) -mapping elements from F i-1 to F i and vice versa at no arithmetic cost; -multiplication and Euclidean division of polynomials of degree at most d in

F i [x] using O(M(d i ))
operations, via Kronecker's substitution, as already done in e.g. [vzGS92]; -computing a (#F j )-th power in F i using O( i-1 M( )) operations, after a precomputation that uses O( M( ) log(q)) operations.

For one fundamental operation, we only have an efficient algorithm in the case = 2, hence we introduce the following notation:

-R(i) is a bound on the expected cost of finding a root of a polynomial of degree in

F i [x].
Note that we allow Las Vegas algorithms here, as no deterministic polynomial time algorithm is known. For = 2, Doliskani and Schost show that R(i) = O(M( i ) log( i q)). For general , we have R(i) = O( i M( i+1 ) log( ) log( q)) using the variant of the Cantor-Zassenhaus algorithm described in [vzGG99, Chapter 14.5], or R(i) = O ( i(ω+1)/2 + M( i+1 log(q)))i log( ) using [KS97]. Here, ω is such that matrix multiplication in size m over any ring can be done in O(m ω ) base ring operations (so we can take ω = 2.38 using the Coppersmith-Winograd algorithm). In any case, R(i) is between linear and quadratic in the degree i .

The Frobenius and the volcano

In this section we explore some fundamental properties of ordinary elliptic curves over finite fields: the structure of their isogeny classes, its relationship with the rational ∞ -torsion points, and with the Frobenius endomorphism π.

Isogeny volcanoes

For an extensive introduction to isogeny volcanoes we refer the reader to [Sut13a]. We recall here, without their proof, two results about -isogenies between ordinary elliptic curves. (i) If O is -maximal then there are (d K / ) + 1 horizontal -isogenies from E (and no ascending -isogenies). (ii) If O is not -maximal then there are no horizontal -isogenies from E, and one ascending -isogeny.

A volcano of -isogenies is a connected component of the graph of rational -isogenies between curves defined on F q . The crater is the subgraph corresponding to curves having an -maximal endomorphism ring. The shape of the crater is given by the Kronecker symbol (d K / ), as per Proposition 2.2. For any k 0, an k -isogeny is horizontal if it is the composite of k horizontal -isogenies. The depth of a curve is its distance from the crater. It is also the -adic valuation of the conductor of O = End(E).

• • • • "Stromboli": (d K / ) = -1 • • • • "Vesuvius": (d K / ) = 0 • • • • • • "Etna": (d K / ) = +1 • • • • • • Figure 1. The three shapes of volcanoes of 2-isogenies

The -adic Frobenius

In the rest of this paper we consider only a volcano with a cyclic crater (i.e. we assume (d K / ) = +1), so that is an Elkies prime for these curves. This implies that the Frobenius automorphism on T (E), which we write π|T (E), has two distinct eigenvalues λ = µ. The depth of the volcano of

F q -rational -isogenies is h = v (λ -µ) [Sut13a, Theorem 7(iv)].
Proposition 2.3. Let E be an ordinary elliptic curve with Frobenius endomorphism π. Assume that the characteristic polynomial of π has two distinct roots λ, µ in Z , so that the -isogeny volcano has a cyclic crater. Then there exists a unique e ∈ 0, h such that π|T (E) is conjugate, over Z , to the matrix λ e 0 µ . Moreover e = h if E lies on the crater, and else h -e is the depth of E in the volcano.

We note here that the matrix λ h 0 µ is conjugate over Z to λ 0 0 µ .

Proof. Since the characteristic polynomial of π splits over Z , the matrix of π|T (E) is trigonalizable. Conjugating the matrix λ a 0 µ by ( 1 b 0 1 ) replaces a by a -b(λ -µ), and conjugating by ( c 0 0 1 ) replaces a by c • a, so that the valuation e = v (a) is an invariant under matrix conjugation. This proves the first part. For the second part, by Tate's theorem [Sil92, Isogeny theorem 7.7 (a)], O ⊗ Z is isomorphic to the order in Q [π ] of matrices with integer coefficients, which is generated by the identity and -min(h,v (a)) (π -λ).

We now study the action of -isogenies on the -adic Frobenius by showing the link between two related notions of diagonalization.

Definition 2.4 (Horizontal and diagonal bases). Let E be a curve lying on the crater. We call a point of E[ k ] horizontal if it generates the kernel of a horizontal k -isogeny. We call a basis of E[ k ] diagonal if π is diagonal in it, horizontal if both basis points are horizontal.

Proposition 2.5. Let E be a curve lying on the crater and P be a point of E[ k ] such that h P is an eigenvector of π. Then h P is horizontal if, and only if, P is an eigenvector for π. If π(P ) = λP then we say that h P has direction λ.

This proposition being trivially true for h k, we assume that k h in what follows. Let R be a point of E of order k , let φ be the isogeny with kernel R , and let E be its image. The subgroup R defines a point in the projective space of E[ k ], which is a projective line over Z/ k Z. There exists a canonical bijection [Ser77, II.1.1] between this projective line and the set of lattices of index k in the Z -module T (E): it maps a line R to the lattice Λ R = R + k T (E). This lattice is also the preimage by φ of the lattice k T (E ).

Fix a basis (P, Q) of E[ k ], let Π be the matrix of π in this basis, and let R = xP + yQ. The lattice Λ R is generated by the columns of the matrix L R = k 0 x

0 k y . The Hermite normal form of L R is M R = k-m x/y 0 m
, where we write y = m y with y , and the columns of M R also generate the lattice Λ R . We check that M R has determinant

k . Since Λ R = φ -1 R ( k T (E )), there exists a basis of T (E ) in which φ R has matrix k M -1 R . Therefore, in that basis of T (E ), the matrix of π|T (E ) is M -1 R • Π • M R . Proof of Proposition 2.5. Fix a basis (R, S) of E[ k ]
that diagonalizes π. We can write P = xR + yS; without loss of generality we may assume y = 1. Let φ be the isogeny determined by h P , and let E be its image. Since h P is an eigenvector of π, φ is a rational isogeny. According to the previous discussion, π|T (E ) has matrix λ h-k x(λ-µ) 0 µ

. This matrix is diagonalizable only if v (x) k -h. On the other hand, we can compute (π -µ)P = x(λµ)R, so that P is an eigenvector on the same condition v (x) k -h.

While horizontal bases are our main interest, diagonal bases are easier to compute in practice. Algorithms computing both kind of bases are given in Section 3. The main tool for this is the next proposition: given a horizontal point of order k , it allows us to compute a horizontal point of order k+1 .

Proposition 2.6. Let ψ : E → E be a horizontal -isogeny with direction λ. For any point

Q ∈ E[ ∞ ], if Q is horizontal with direction µ, then ψ(Q) is horizontal with direction µ.
Proof. Let Q = ψ(Q) and ψ be the isogeny dual to ψ. Since both ψ and ψ(Q ) = Q are horizontal with direction µ, Q is also horizontal.

Proposition 2.7. Let ψ : E → E be an isogeny of degree r prime to .

(i) The curves E and E have the same depth in their -isogeny volcanoes.

(ii) For any point P ∈ E[ k ], the isogenies with kernel P and ψ(P ) have the same type (ascending, descending, or horizontal with the same direction). (iii) If P ∈ E[ ] and P ∈ E [ ] are both ascending, or both horizontal with the same direction, then E/P and E /P are again r-isogenous.

Proof. Points (i) and (ii) are consequences of Proposition 2.3 and of the fact that ψ, being rational and of degree prime to , induces an isomorphism between the Tate modules of E and E , commuting to the Frobenius endomorphisms. For point (iii), we just note that since there exists a unique subgroup of order which is either ascending or horizontal with a given direction, we must have P = ψ(P ) .

Galois classes in the -torsion

Assume that E has a -maximal endomorphism ring. The following proposition summarizes the properties of E[ k ] that we will need for our main interpolation algorithm. If is odd, let α = v (λ -1 -1) and β = v (µ -1 -1); if = 2, let α = v 2 (λ 2 -1) -1 and β = v 2 (µ 2 -1) -1, and assume without loss of generality that α β. Since λ ≡ µ (mod h+1 ), it is impossible that λ ≡ µ ≡ 1 (mod h ), so that one at least of the two valuations α, β is h, and therefore β h. Proposition 2.8. For any k, let d k be the degree of the smallest field extension F/F q such that E[ k ] ⊂ E(F ). Then:

(i) The order of q in (Z/ Z) × divides d 1 , and d 1 divides ( -1).

(ii) If is odd then for all k 1, d k = min(v (d1),k-β) .

(iii) If = 2 then d 2 ∈ {1, 2} and, for all k 2, d k = min(v (d2),k-β) .

(iv) Let [F :

F q ] = d 1 n , the group E[ ∞ ](F ) is isomorphic to (Z/ n+α Z) × (Z/ n+β Z). (v) The group E[ k ] contains at most k • k+β Galois conjugacy classes over F 1 = F q d 1 .
Proof. The degree d k is exactly the order of the matrix π|E[ k ]. It is therefore the least common multiple of the multiplicative orders of λ, µ modulo k . This proves (i) using the fact that λ • µ = q. For points (ii)-(v) we may assume that d 1 = 1. Then, for any

N , v (λ 2N - 1) = α + v (2N ). Let (P, Q) be a diagonal basis of E[ k ]. The point (π N -1)(xP + yQ) = (λ N -1)xP + (µ N -1)yQ is zero iff v (x) + α + v (N ) k and v (y) + β + v (N ) k.
This shows (iv). The largest Galois classes are those for which v (y) = 0 and their size is k-β , proving (ii) and (iii). Moreover, for any i k -β the points in an orbit of size i are those for which v (x) k -α -i and v (y) k -β -i; there are at most min(α+i,k)+min(β+i,k) such points, and therefore min(α+i,k)+min(β,k-i) k-i+β corresponding classes. Summing this over all i proves (v).

Computing the action of the Frobenius endomorphism

We continue here our study on the action of the Frobenius π on E[ k ]. Given an ordinary elliptic curve E with -maximal endomorphism ring, we explicitly compute diagonal and horizontal bases of E[ k ] as defined in the previous section. We will use the latter basis of E[ k ] in Section 5.2, to put restrictions on the interpolation problem of our algorithm.

We suppose that k h. By Proposition 2.8, there exists a Kummer tower F 0 ⊂ • • • ⊂ F k-β such that all the points of E[ k ] are rational over F k-β . The algorithms presented next assume that the tower has already been computed.

Computation of a diagonal basis

In Algorithm 1 below, we describe how to compute eigenvalues of the Frobenius mod k and corresponding eigenvectors in the k -torsion subgroup. We write Q ← divide( , P ) for the computation of a preimage of P by multiplication by .

Algorithm 1 Computing a diagonal basis of E[ k ]

Input: E: an ordinary, -maximal elliptic curve; k: a positive integer; Output:

(P k , Q k ): a basis of E[ k ]; λ, µ ∈ Z/ k Z such that π(P k ) = λP k , π(Q k ) = µQ k . 1: λ ← 0; µ ← 0; P 0 , Q 0 ← neutral element of E[ ]. 2: for i = 0 to k -1 do 3: P ← divide( , P i ); Q ← divide( , Q i ). 4: compute π|(P , Q ) = λ+a i b i c i µ+d i (mod i+1 ). 5: if b = 0 then x ← 0; solve equation c i + ((d -a) i + µ -λ)y = 0; 6: else solve equation c i x 2 + ((d -a) i + µ -λ)x -b i = 0; y ← -cx/b; end if.
7:

P i+1 ← P + yQ ; Q i+1 ← xP + Q . 8: λ ← λ + i (a + bx); µ ← µ + i (d + cy). 9: end for 10: return (P k , Q k , λ, µ). Proposition 3.1. Algorithm 1 computes a diagonal basis of E[ k ] using an expected O(R(k -β) + 2 M( k-β ) + M( 2 ) log( ) log( q)) operations in F q .
Proof. The equation at line 5 or 6 is first divided out by the largest power of possible, which is min(h,i) , then solved modulo . For i h -1, since a = d and b = c = 0, the solutions are x = y = 0, and steps 5 to 7 do nothing. A straightforward calculation shows that after each loop the basis (P i+1 , Q i+1 ) is diagonal.

For i = 0, the basis of E[ ](F 1 ) at step 3 is computed by factoring the -division polynomial at an expected cost of O( M( 2 ) log( ) log( q)) operations using the Cantor-Zassenhaus algorithm. Once E[ ] has been computed, we can factor the multiplication-by-map as a product of two -isogenies. Then, for any P defined in E(F i-β ), the computation of divide( , P ) at Step 3 costs O(R(i -β + 1)) operations. Evaluating π(P ) in Step 4 has a cost of O( i-β M( )).

Writing π(P ) as a linear combination αP + βQ needs at most 2 point additions, with a cost of 2 M( i-β+1 ). The cost of solving the equations at Steps 5 and 6 by exhaustive search is negligible, as are the remaining operations. Since the cost of each loop grows geometrically, the last loop dominates all others, and gives the stated complexity.

Computation of a horizontal basis

Using the previous algorithm we can compute a diagonal basis of E[ h+1 ]. By Proposition 2.5, this gives us a horizontal basis of E[ ]. Thanks to Proposition 2.6, we can use this information to improve horizontal points of E[ i ] into horizontal points of E[ i+1 ], as illustrated in Algorithm 2. Proposition 3.2. Algorithm 2 is correct and computes its output using an expected

O(R(k -β) + kR(h -β + 1) + k 2 M( h-β+1 )) operations in F q .
Proof. Let E i be the image curve of φ i . We check that at step i of the loop, the points (P i , Q i ) form a diagonal basis of E i [ h+1 ], and φ i has direction λ. The fact that R is horizontal is then a consequence of Proposition 2.6. The two most expensive operations in the Algorithm 2 Computing a horizontal point of order k Input: (P 0 , Q 0 ): a diagonal basis of E[ h+1 ]; k: an integer, k h + 1. Output: R: a horizontal point of E[ k ] with direction λ.

1: for i = 1 to k -1 do 2:

φ i ← isogeny with kernel h P i-1

3:

Q i ← φ i (Q i-1 )
4:

P ← divide( , φ i (P i-1 )).

5:

Write π(P ) = λP + bQ i for b ∈ Z/ Z and let

P i ← P -(b/µ)Q i . 6: end for 7: return R = φ 1 • . . . • φ k-1 (divide( k-(h+1) , P k-1 )).
loop are Steps 4 and 5, costing respectively O(R(h -β + 1)) and O( 2 M( h-β+1 )), as discussed in the proof of Proposition 3.1. They are repeated k times. Finally, Step 7 is dominated by the last divide operation, which costs O(R(k -β)).

One application of Algorithm 1 (with input k ← h + 1) and two applications of Algorithm 2 allow us to compute a horizontal basis of E[ k ]. This could be done directly with Algorithm 1 instead, but that would require computing in an extension F k+h-β .

Interpolation step

After constructing bases (P, Q) of E[ k ] and (P , Q ) of E [ k ] using the algorithms of the previous section, our algorithm computes the polynomial with coefficients in F q mapping x(P ) to x(P ), x(Q) to x(Q ), and the other abscissas accordingly. In this section we give an efficient algorithm for this specific interpolation problem. The algorithm appeared in [DF11] in the context of the Artin-Schreier extensions used in Couveignes' isogeny algorithm; it uses original ideas from [EM03]. We recall this algorithm here, and adapt the complexity analysis to our setting of Kummer extensions.

We start by tackling a simpler problem. We suppose we have constructed a tower of Kummer extensions

F q = F 0 ⊂ F 1 ⊂ • • • ⊂ F n , with [F 1 : F 0 ] | ( -1), and [F i+1 : F i ] = for any i > 0.
Given two elements v, w ∈ F n \ F n-1 , we want to compute polynomials T and L such that:

-

T ∈ F q [x] is the minimal polynomial of v, of degree d = deg T < n ; -L is in F q [x]
, of degree less than d, and

L(v) = w. Observe that, since v, w / ∈ F n-1 , we necessarily have v (d) = n -1, so that n-1 d < n .
Using a fast interpolation algorithm [vzGG99, Chapter 10.2], the polynomials T and L could be computed in O nM( 2n ) log( ) operations in F q . We can do much better by exploiting the form of the Kummer tower, and the Frobenius algorithm given in Lemma 1.1.

Following [DF11], we first compute T , starting from T (0) = x -v. We let σ i be the map that takes all the coefficients of a polynomial in F n-i [x] to the power #F n-i-1 . For i = 0, . . . , n -1, suppose we know a polynomial T (i) of degree i in F n-i [x]. Then, compute the polynomials T (i,j) given by T (i,j) = σ j i T (i) for 0 ≤ j ≤ -1, and define

T (i+1) = b j=0 T (i,j) with b = -1 if i < n -1, d/ n-1 otherwise. (4.1)
One easily sees that T (i+1) is the minimal polynomial of v over F n-i+1 .

Lemma 4.1. The cost of computing T is O(nM( n+1 ) log( )) operations in F q .

Proof. At each step i, from the knowledge of T (i) we compute all T (i,j) using Lemma 1.1. The cost for a single polynomial T (i,j) is of O( i n-i-1 M( )) operations, i.e. O( n M( )) for all O( ) of them. From the T (i,j) 's we compute T (i+1) using a subproduct tree, as in [vzGG99, Lemma 10.4]. The result has degree O( i+1 ) and coefficients in F n-i , thus the overall cost is O(M( n+1 ) log( )). After T (i+1) is computed this way, we can convert its coefficients to F n-i-1 at no algebraic cost. Summing over all i, we obtain the stated complexity.

We can finally proceed with the interpolation itself. First, compute w = w/T (v) and let L (0) = w . Next, for i = 0, . . . , n -2, suppose we know a polynomial L (i) in F n-i [x] of degree less than i . We compute the polynomials L (i,j) given by L (i,j) = σ j i L (i) and

L (i+1) = b j=0 L (i,j) T (i+1)
T (i,j) , b defined as in Eq. (4.1).

As shown in [DF11], L (n) is the polynomial L we are looking for.

Proposition 4.2. Given v, w ∈ F n \ F n-1 , the cost of computing the minimal polynomial T ∈ F q [x] of v and the interpolating polynomial

L ∈ F q [x] such that L(v) = w is O(nM( n+1 ) log( )) operations in F q .
Proof. After the polynomials T (i) have been computed, we need to compute T (v). This is done by means of successive Euclidean remainders, since T (v) = (((T mod T (1) ) mod

T (2) ) • • • mod T (n) ). At stage i, we have to compute the Euclidean division of a polynomial of degree O( n-i+1 ) by one of degree O( n-i ) in F i [x].
Using the complexities from Section 1.3 we deduce that each division can be done in time O(M( n+1 )), for a total of O(nM( n+1 )) operations. Then, computing w = w/T (v) takes O(M( n ) log( n )) operations.

Finally, at each step i, the polynomials L (i,j) are computed at a cost of O( n M( )), as in the proof of Lemma 4.1. The computation of L (i+1) uses the same subproduct tree as for the computation of T (i) , requiring O(log ) additions, multiplications and divisions of polynomials of degree O( i+1 ) with coefficients in F n-i , for a total of O(M( n+1 ) log( )). Summing over all i, the complexity statement follows readily.

We end with the general problem of interpolating a polynomial in F q [x] at points of F n .

Proposition 4.3. Let (v 1 , w 1 ), . . . , (v s , w s ) be pairs of elements of F n , let t i be the degree of the minimal polynomial of v i , and let t = t i . The polynomials -T ∈ F q [x] of degree t such that T (v i ) = 0 for all i, and -L ∈ F q [x] of degree less than t such that L(v i ) = w i for all i can be computed using O M(t) log(s) + nM( 2 t) log( ) operations in F q .

Proof. The polynomial T is simply the product of all the minimal polynomials T i . Let n i = v (t i ), so that v i , w i ∈ F ni+1 \ F ni , and ni t i < ni+1 . We convert (v i , w i ) to a pair of elements of F ni+1 at no algebraic cost, then we compute T i as explained previously at a cost of O(nM( ni+2 ) log( )) operations. Bounding ni by t i , summing over all i, and using the superlinearity of M, we obtain a total cost of O(nM( 2 t) log( )) operations. Simultaneously, we compute all the polynomials L i such that L i (v i ) = w i , at the same cost.

Then we arrange the T i 's into a binary subproduct tree and multiply them together. A balanced binary tree, though not necessarily optimal, has a depth of O(log(s)), and requires O(M(t)) operations per level. Thus we can bound the cost of computing T by O(M(t) log(s)).

Finally, using the same subproduct tree structure, we apply the Chinese remainder algorithm of [vzGG99, Chapter 10] to compute the polynomial L at the same cost O(M(t) log(s)).

The complete algorithm

We finally come to the description of the full algorithm. Given two j-invariants, defining two elliptic curves E and E , and an integer r, we want to compute an isogeny ψ : E → E of degree r. Since the algorithms of Section 3 apply to curves on top of volcanoes with cyclic crater, we first need to determine a small Elkies prime for E and E , and then reduce to an explicit isogeny problem on the crater of the -volcanoes. These steps are discussed and analyzed next.

Finding a suitable -volcano

Our algorithm uses an Elkies prime . Since d K is not assumed to be known yet, we need to be able to compute the height h of the volcano, the shape of its crater, as well as the shortest -isogeny chain from E to the crater.

The algorithms of Fouquet and Morain [FM02] compute the height h and find a curve E max on the crater at the cost of O( h 2 ) factorizations of the -th modular polynomial Φ . The polynomial Φ is computed using Õ( 3 log( )) boolean operations, then each factorization costs an expected O(M( ) log( ) log( q)) operations using the Cantor-Zassenhaus algorithm (more efficient methods for special instances of volcanoes are presented in [MMRV05] and in [IJ13], but we do not discuss them). Working on E and E , we compute the shortest path of -isogenies α : E → E max , α : E → E max linking the curves E, E to the craters. We still have to determine the shape of these craters. Since the height h of the volcano is known, using Algorithm 1 we can compute a matrix of π|E max [ h+1 ]. If this matrix has two distinct eigenvalues then the crater is cyclic, otherwise it is not.

By Proposition 2.7, the depth of E and E below their respective craters is the same. By Proposition 2.7 (iii), the curves E max and E max are again r-isogenous; we can use our algorithm to compute such an isogeny ψ max . Then, since is coprime to r, ψ = (α ) -1 • ψ max • α is well defined and is the required r-isogeny. Its kernel can be computed in O(hM( r) log( r)) operations by evaluating the dual isogeny α on the kernel of ψ max via a sequence of resultants.

Interpolating the isogeny

We now assume that both curves E, E have -maximal endomorphism rings. We fix bases of E[ k ], E [ k ] and write π, π for the matrices of the Frobenius. Since ψ is rational, its matrix satisfies the relation π

• ψ = ψ • π in Z 2×2 and hence in (Z/ k Z) 2×2 . If diagonal bases of E[ k ], E [ k ]
are used, then, since π is a cyclic endomorphism of Z 2 , this condition seems to ensure that ψ is a diagonal matrix; however, Z/ k Z is not an integral domain and π is congruent, modulo h , to the scalar matrix λ, so we can only say that ψ (mod k-h ) is diagonal. If on the other hand we choose horizontal bases of E[ k ], E [ k ] then, by Proposition 2.7 (ii), we know that ψ is a diagonal matrix.

We then enumerate all the 2k-2 invertible diagonal matrices; for each matrix M , we interpolate the action of M on E[ k ] as a rational fraction, and verify that it is an r-isogeny. The successful interpolation will be our explicit isogeny ψ. Precisely, we interpolate using the abscissas of non-zero points of E[ k ]; there are ( 2k -1)/2 distinct such abscissas (or 2 2k-1 + 1 when = 2). The isogeny ψ acts on abscissas as a rational fraction of degrees (r, r -1), which is thus defined by 2r coefficients; knowing this rational function allows us to find the kernel of ψ, and recover ψ itself using Vélu's formulas. For this method to work, we therefore select the smallest k h + 1 such that 2k -1 > 4r.

Summarizing, our algorithm for two -maximal curves proceeds as follows:

(1) Use Algorithms 1 and 2 to compute horizontal bases (P, Q), Proposition 5.1. Assuming that h < √ r, the algorithm above computes an isogeny ψ : E → E in expected time O r 2 M(r 4 ) + M(r 3 ) log( q) log(r) log( ) .

(P , Q ) of E[ k ], E [ k ]; (
Proof. By definition of k, we know that 2k ∈ O(r 2 ). By Proposition 2.8, there is a β < h such that E[ k ] is contained in E(F n ) with n = k -β. We thus construct the Kummer tower F 0 ⊂ • • • ⊂ F n , and we do the precomputations required by Lemma 1.1 at a cost of O( M( ) log(q)).

Bounding h by k -1, Step (1) costs on average O(kR(k -β) + k 2 M( √ r) + M( 2 ) log( ) log( q)) according to Propositions 3.1 and 3.2. Using the most pessimistic estimates of Section 1.3, we see that this cost is bounded by O(M(r 3 ) log(r) log( ) log( q)).

By Proposition 2.8 (v), there are at most O(k

• k+β ) Galois classes in E[ k ].
In order to apply the algorithms of Section 4, we need to compute a representative for each class. Each representative is computed from the basis (P, Q) using point multiplication by two scalars k in the field F n , which costs O(M( n ) log( k )) operations. We thus have a total cost of O(kM( 2k ) log( k )) ⊂ O(M(r 2 ) log(r) 2 ) to compute all such representatives.

Then, using Proposition 4.3, where the total degree is t = ( 2k -1)/2 ∈ O(r 2 ), and the number of interpolation points is s ∈ O(k • k+β ), we can compute the polynomials T and L a,b at a cost of O(M(r 4 ) log(r) log( )). The cost of computing F a,b , and identifying the isogeny, is dominated by that of computing L a,b [DF11, §3.3]. Finally, in general approximately 2k = O(r 2 ) candidate matrices must be tried before finding the isogeny.

Overall complexity

By a result of Shparlinski and Sutherland [SS14, Theorem 1], for almost all primes q and curves E/F q , for L log(q) ε for any ε > 0, asymptotically half of the primes L are Elkies primes. Hence, we expect to have enough small Elkies primes to apply our algorithm. The following theorem states a worst case bound depending on r and q alone. Theorem. For almost all primes q and curves E, E over F q , it is possible to solve the "Explicit Isogeny Problem" in expected time O rM(r log(q) 6 ) log(r) loglog(q) . Proof. Given a curve E, we search for the smallest Elkies prime satisfying the conditions of Proposition 5.1. As a special case of [SS14, Theorem 1], we can take L ∈ O(log(q)) such that the product of all Elkies primes L exceeds Ω( √ q). On the other hand, we discard those primes L for which the height h satisfies h > √ r; since those discarded primes are divisors of √ d K , their product is at most O( √ q). This shows that there remains enough "good" Elkies primes in 1, L , so that in the worst case ∈ O(log(q)).

The most expensive steps in Section 5.1 are the computation and the factorization of the modular polynomials for all primes up to . This is well within O(log(q) 6 ). The stated complexity follows then from substituting = O(log(q)) in Proposition 5.1.

Conclusion and experimental results

In the previous sections we have obtained a Las Vegas algorithm with an interesting asymptotic complexity. In particular, in the favorable case where = O(1), the running time interesting to generalize the concept of horizontal bases to any curve. Second, a multi-modular approach interpolating on a torsion group of composite order is certainly possible, and could improve the running time of our algorithm by allowing it to work in smaller extension fields.

  Proposition 2.1[Koh96, Proposition 21]. Let φ : E → E be an -isogeny between ordinary elliptic curves and O, O be their endomorphism rings. Then one of the three following cases is true:(i) [O : O] = ,in which case we call φ ascending; (ii) [O : O ] = , in which case we call φ descending; (iii) O = O, in which case we call φ horizontal. Proposition 2.2 [Koh96, Proposition 23]; [Sut13a, Lemma 6]. Let E be an ordinary elliptic curve with endomorphism ring O.

  2) Compute the polynomial T vanishing on the abscissas of P, Q as in Section 4;(3) For each invertible diagonal matrixa 0 0 b in (Z/ k Z) 2×2 : (i) compute the interpolation polynomial L a,b such that L a,b (x(uP + vQ)) = x(a u P + b v Q ) for all u, v ∈ Z/ k Z; (ii)Use the Cauchy interpolation algorithm of [vzGG99, Chapter 5.8] to compute a rational fraction F a,b ≡ L a,b (mod T ) of degrees (r, r -1); (iii) If F a,b defines an isogeny of degree r, return it and stop.

Acknowledgements. We would like to thank the anonymous referees for their careful review and their insightful remarks.

of the algorithm is quasi-quadratic in the isogeny degree r and quasi-linear in log q. Thus we expect it to be practical, and a substantial improvement over Couveignes' original algorithm, at least when small parameters and h can be found quickly. A large or h adversely affects performance in the following ways:

-All modular polynomials up to Φ must be computed or retrieved from tables.

-All degrees ( 2k -1)/4 r < ( 2k+1 -1)/4 require essentially the same computational effort, thus resulting in a staircase behavior when r increases. -Because we must have k > h, all degrees r smaller than ( 2h+2 -1)/4 require the same computational effort. For these reasons, it is wisest in practice to set small a priori bounds on and h, and only run our algorithm when parameters within these bounds can be found.

To validate our findings, we implemented a simplified version of our main algorithm using SageMath v7.1 [Dev16]. In our current implementation, we only handle the case = 2 and we work only with curves on the crater of a 2-volcano. We implemented the construction of Kummer towers described in [DS15], in the favorable case where p = 1 mod 4. Source code and benchmark data are available in the GitHub project https://github.com/Hugounenq-Cyril/ Two_curves_on_a_volcano/.

We ran benchmarks on an Intel Xeon E5530 CPU clocked at 2.4GHz. We fixed a base field F q and an elliptic curve E with height h = 3 and β = 2, then ran our algorithm to compute the multiplication-by-r isogeny E → E, for r increasing. The torsion levels involved in the computations varied from 2 3 to 2 8 . Figure 2 (left) shows the running times for the computation of the horizontal basis of E[ k ], and for one execution of the interpolation step. Running times are close to linear in r, as expected. The staircase behavior of our algorithm is apparent from the plot. Since the interpolation steps must be repeated ∼ r times, we focus on this step to compare the running time for different base fields. In Figure 2 (right) we observe that the dependency in q, although much better than in Couveignes' original algorithm, is higher than what the theoretical analysis would predict. This may due to low-level implementation details of SageMath, which, in the current implementation, are beyond our control.

In conclusion, our algorithm shows promise of being of practical interest within selected parameter ranges. Generalizing it to work with Atkin primes would considerably enlarge its applicability range; we hope to develop such a generalization in a future work. On the practical side, we plan to work on two improvements that seem within reach. First, the reduction from generic curves to -maximal curves seems superfluous and unduly expensive: it would be

We give here the full decomposition of E[ k ] in Galois classes. This is a more precise form of Proposition 2.8 (v).

Proposition A.1. Let E be an elliptic curve with -maximal endomorphism ring. Assume = 2, λ ≡ µ ≡ 1 (mod ) and let α = v (λ -1), β = v (µ -1). Write ν(x, y) = min(x + y, x + β -1, y + α -1) and ρ(x, y) = x + y -ν(x, y) = max(0, x -α + 1, y -β + 1). The decomposition of the group E[ k ] in Galois classes is as follows:

(i) for i, j = 1, . . . , k -1: ( -1) 2 • ν(i,j) classes of size ρ(i,j) ; (ii) for i = 1, . . . , k -1: ( -1) • min(i,α-1) classes of size max(0,i-α+1) , and ( -1) • min(i,β-1) classes of size max(0,i-β+1) ; (iii) the 2 singleton classes of E[ ].

Proof. Fix a basis (P, Q) of E[ k ] such that π(P ) = λP , π(Q) = µQ. Studying the Galois orbits of E[ k ] means studying the map Z 2 → Z 2 , (x, y) → (λx, µy). In other words, the orbits correspond to elements of Z 2 modulo the multiplicative subgroup generated by (λ, µ). An easy way to describe this is to consider a multiplicative lattice in (Q × ) 2 .

Let ξ be a primitive ( -1)-th root of unity in Z . Then by [Ser70, Théorème II.3.2], the map f (x, y, z)

Since λ ≡ 1 (mod ), we may write λ = f (0, 0, u α-1 ) and µ = f (0, 0, v β-1 ) for some u, v ∈ Z × . This implies that the set W (i, j, c, d) is stable under Galois. Moreover, the orbits of W (i, j, c, d) correspond bijectively to points of a fundamental domain of the lattice Λ i,j generated by the columns of i 0 u α-1 0 j v β-1 , whereas the size of each orbit is [(Z/ i Z) × (Z/ j Z) : Λ i,j ]. By using elementary column manipulations, we find that the covolume of Λ i,j is ν(i,j) , hence the point (i) of the proposition. (The case i = j = 0 yields singleton classes in E[ ]).

The union of all the sets W (j, i, c, d) is exactly the set of all xP + yQ for x, y = 0. We obtain the classes of (ii) by considering the sets V (i, c) • P and V (j, d) • Q.

We now state the equivalent proposition when = 2. The proof is much the same as in the odd case.

Proposition A.2. Let E be an elliptic curve with 2-maximal endomorphism ring. Assume λ ≡ µ ≡ 1 (mod 4) and let α

classes of size 2 max(0,i-α+2) , and 4 • 2 min(i,β-2) classes of size 2 max(0,i-β+2) . (iii) the 16 singleton classes of E[4].

Note that if λ or µ ≡ -1 (mod 4) then by replacing the base field by a quadratic extension, we can always ensure that the condition λ ≡ µ ≡ 1 (mod 4) is satisfied.


Mohammad Amin Farvardin
email: amin.farvardin@teledetection.fr

Eric Kergosien
email: eric.kergosien@univ-lille3.fr

Mathieu Roche
email: mathieu.roche@cirad.fr

Maguelonne Teisseire
email: maguelonne.teisseire@teledetection.fr

[Demo] A webtool for analyzing land-use planning documents

Keywords: Land-use planning, Web application, Geospatial features

. In this paper, we present the Web application, SentiAnnotator, based on NLP methods to extract and visualize geospatial information with the associated entities. The evaluation of our application shows good results on a French corpus, i.e. F-measure of 0.74 and 0.75 respectively for the identification of spatial features and organizations.

Introduction

Researchers and experts of land-use planning are looking for decisional tools for helping them to have an overview of user's awareness on territories. In this context, we defined the Opiland method that enables to semi-automatically analyze sentiments related to land-use planning documents [START_REF] Kergosien | Are opinions expressed in land-use planning documents[END_REF]. In this paper, we present the developed software and the associated web services for discovering and for integrating meaning in free texts available on the Web. This kind of textual data (e.g. blogs, newspapers, and so on) is generally complex but useful for public policy dialogue and decision-making. We thus propose an approach that enables (i) to automatically extract features related to land-use planning, and (ii) to give to experts the possibility of evaluating sentiments related to geospatial features, with the ultimate objective of evaluating the policy impact for adapting their decisions. The main originality of our software concerns the integration of different levels of semantics present in a document. This is really crucial in order to improve the analysis of information, specially for land-use planning domain. Generally in the opinion mining field, the connection between opinion and topic is studied. Actually in the land-use planning domain, it is necessary to take into account a larger number of relevant elements like spatial in : Proceedings of the ISWC 2015, Bethlehem, 11/10/2015 features and organizations. Our software offers this possibility for helping the experts to do a finer analysis of Web data.

In this demo paper, we present the web application4 to extract different features related to land-use planning. Hereafter, in Section 2, we focus more precisely on the deployment of natural language processing methods to extract geospatial information, i.e. spatial features and organizations. The web application for uploading, indexing, and marking textual documents is detailed in Section 3. Finally, after a quick look to our system evaluation in Section 4, future work related to our project is drawn in Section 5.

Geospatial information extraction

Named Entity Recognition (NER) methods identify different types of Named Entities (NE): dates, people, organizations, themes, numeric values, as well as locations. There is a significant number of available systems, such as OpenNLP5 , OpenCalais6 , and CasEN [START_REF] Maurel | Casen: a transducer cascade to recognize french named entities[END_REF]. To recognize Named Entities several approaches are based on supervised learning methods. In this context, a bag-of-words representation is often used [START_REF] Carreras | A simple named entity extractor using adaboost[END_REF]. But this kind of statistical approach is not adapted for small data sets we are faced with in the land-use planning domain. Other approaches based on symbolic methods concern geoparsing [START_REF] Gaio | Towards heterogeneous resources-based ambiguity reduction of sub-typed geographic named entities[END_REF][START_REF] Leidner | Detecting geographical references in the form of place names and associated spatial natural language[END_REF][START_REF] Lesbegueries | Associating spatial patterns to textunits for summarizing geographic information[END_REF]. The work of [START_REF] Lesbegueries | Associating spatial patterns to textunits for summarizing geographic information[END_REF] proposes linguistic patterns to extract Spatial Features (SF) from texts. These patterns are based on a cognitive model where SF is composed of at least one NE and one variable number of spatial indicators specifying its location. Five spatial relation types are considered: orientation, distance, adjacency, inclusion, and geometric which defines union or intersection linking two SF. In our proposal, we add new patterns to improve the automatic identification of SF (absolute spatial features (A SF) and relative spatial features (R SF) [START_REF] Kergosien | Are opinions expressed in land-use planning documents[END_REF][START_REF] Lesbegueries | Associating spatial patterns to textunits for summarizing geographic information[END_REF]). The SF annotation is based on the classical typology of the domain and more precisely on the sub-types of locations. Locations can be polysemous: human constructions (e.g. buildings) and addresses (e.g. streets). To take into account all these language specificities, some rules (patterns) have been added.

Moreover we propose a new type of patterns to identify Organizations (OE) which is a specific NE useful for land-use planning domain. The addition of specific rules enables to identify OE which could be confused with SF in documents. Such rules are: (1) an OE is followed by an action verb; (2) an OE is proceeded by prepositions: with, by, for, on behalf of, etc.

In order to manage these geospatial information, we developed the web application SentiAnnotator (http://siso.teledetection.fr/viewer.jsp). A screenshot is presented Figure 1. The web services use the Gate system 7 . After uploading a corpus (in French for this current version), Spatial Features and Organizations are extracted using the implemented rules. Moreover other concepts are extracted using Gate: (i) thematics based on a lexicon using Agrovoc thesaurus 8 , (ii) Opinions related to land-use planning domain [START_REF] Kergosien | Are opinions expressed in land-use planning documents[END_REF].

SentiAnnotator Web application

The web application (Figure 1) allows users to upload corpora, to index documents with specific web services in order to mark different kinds of information (spatial features, organizations, opinions, and themes), to visualize, to correct the results, and to download validated results in XML format. More specifically, it is possible to upload corpora (frame 1), each marked corpus is saved on the server and automatically available in the web application (frame 2). After having downloaded documents, users can select the marked features (frame 5), see the results on the selected documents in frame 3. In this frame, spatial features are in blue color, organizations in purple color, the positive opinions in green color, negative ones in red color and neutral in yellow color. By selecting different categories from frame 5, the related marked information will be kindles in frame 3 and listed by type in frame 4. In case of finding any mistakes, users can unselect marked information (frame 4). Finally expert can export the selected corrected documents by clicking the top right bottom. The downloaded corpus consists of selected documents with the marked information except those were removed by the user. The administration page allows users to upload, edit, and delete pipelines defined in the Gate format. It is also possible to remove processed corpora and to edit the uploaded pipeline rules and the available lexicons.

Evaluation

Three experts of the project evaluated the process for extracting geospatial information by using SentiAnnotator application. We use a French corpus composed of words (71 spatial features and 117 organizations). The evaluations (with classical measure, i.e. Precision, Recall, and F-measure) have been investigated by comparing the manual extraction done by experts with the web service results. For SF, we obtain an excellent recall (0.91) and an acceptable precision (0.62), the F-measure is 0.74. We extract the great majority of SF but the rules still return some errors. The rules to identify OE are very efficient and return high precision (0.85) but the value of recall is lower (0.67). The F-measure for organization identification is 0.74. The rules for organization extraction seem well-adapted to the domain but they have to be extended in order to improve the recall that remains low.

Conclusion and Future Work

In this paper, we have presented a Web application called SentiAnnotator including web services (1) to annotate corpora with features related to landuse planning, and (2) to evaluate achieved approaches with experts. Experts are using this tool for analyzing the construction project of a road around Villeveyrac (France). Future work will be dedicated to the improvements of the defined linguistics patterns for discovering NE in order to tackle the issues related to the land-use planning specificities and the multilingual aspects. We also plan to extend our approach to different types of textual contents such as tweets.

Fig. 1 .

 1 Fig. 1. SentiAnnotator Web application 8 http://aims.fao.org/fr/agrovoc

http://siso.teledetection.fr/

https://opennlp.apache.org/

http://www.opencalais.com/

https://gate.ac.uk/ in : Proceedings of the ISWC 2015, Bethlehem, 11/10/2015

Acknowledgments: The authors thank Midi Libre (French newspaper) for its expertise on the corpus and all partners of the Senterritoire project for their involvement (MSH-M, Geosud Equipex, Numev Labex, and Tectoniq PEPS project).