Computing separable isogenies in quasi-optimal time

Abstract: Let

A

be an abelian variety of dimension

g

together with a principal polarization

p h i : A i g h t a r r o w h a t A

defined over a field

k

. Let

e l l

be an odd integer prime to the characteristic of

k

and let

K

be a subgroup of

A [e l l]

which is maximal isotropic for the Riemann form associated to

p h i

. We suppose that

K

is defined over

k

and let

B = A / K

be the quotient abelian variety together with a polarization compatible with

p h i

. Then

B

, as a polarized abelian variety, and the isogeny

f : A i g h t a r r o w B

are also defined over

k

. In this paper, we describe an algorithm that takes as input a theta null point of

A

and a polynomial system defining

K

and outputs a theta null point of

B

as well as formulas for the isogeny

f

. We obtain a complexity of

i l d e O (e l l^{f r a c r g 2})

operations in

k

where

r = 2

(resp.

r = 4

) if

e l l

is a sum of two squares (resp. if

e l l

is a sum of four squares) which constitutes an improvement over the algorithm described in [7]. We note that the algorithm is quasi-optimal if

e l l

is a sum of two squares since its complexity is quasi-linear in the degree of

f

.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Computing separable isogenies in quasi-optimal time