[top] [TitleIndex] [WordIndex]


Speaker: Francois Morain

Title: Fast algorithms for computing isogenies between elliptic curves

Isogenies are at the heart of the SEA algorithm that computes the
cardinality of an elliptic curve over a finite field. We will survey
the different algorithms computing isogenies, insisting on the large
characteristic case. We will give a fast variant for an algorithm
originally due to Elkies: an isogeny of degree $\ell$ may be computed
in quasi-linear time. We will also describe an auxiliary algorithm
that computes the first $n$ coefficients of the Weierstrass $\wp$
function in quasi-linear time too. This is joint work with A.~Bostan,
B.~Salvy and \'E.~Schost as described in our Math. Comp. paper.

2013-05-11 18:32