As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic $p$, there exists an algorithm that computes, for $\ell$ an Elkies prime, $\ell$-torsion points in an extension of degree $\ell -1$ at cost $\tilde{O}(\ell max{(\ell ,logq)}^2)$ bit operations in the favorable case where $\ell \le p/2$.We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the $p$-adic approach followed by Joux and Lercier to get an algorithm valid without any limitation...

We generalize the concept of reduced Arakelov divisors and define C-reduced divisors for a given number C ≥ 1. These C-reduced divisors have remarkable properties, similar to the properties of reduced ones. We describe an algorithm to test whether an Arakelov divisor of a real quadratic field F is C-reduced in time polynomial in $log|{\Delta }_F|$ with ${\Delta }_F$ the discriminant of F. Moreover, we give an example of a cubic field for which our algorithm does not work.

In this article the discrete logarithm problem in degree 0 class groups of curves over finite fields given by plane models is studied. It is proven that the discrete logarithm problem for non-hyperelliptic curves of genus 3 (given by plane models of degree 4) can be solved in an expected time of $\tilde{O}\left(q\right)$, where $q$ is the cardinality of the ground field. Moreover, it is proven that for every fixed natural number $d\ge 4$ the following holds: We consider the discrete logarithm problem for curves given by plane models...