Satoh's algorithm for counting the number of points of an elliptic curve
with
is the fastest known algorithm when
is fixed: it computes the invertible eigenvalue
of the Frobenius to
-adic precision
in time
. Since by Hasse's bound, recovering
requires working at precision
, the point counting complexity is of
, quasi-quadratic in the degree
.
Unfortunately, the term
in the complexity makes Satoh's algorithm suitable only for smaller
. For medium sized
, one can use Kedlaya's algorithm which cost
or a variant by Harvey's which cost
, which have a better complexity on
but a worse one on
. For large
, the SEA algorithm costs
.
In this talk, we improve the dependency on
of Satoh's algorithm while retaining the dependency on
to bridge the gap towards medium characteristic. We develop a new algorithm with a complexity of
. In the particular case where we are furthermore provided with a rational point of
-torsion, we even improve this complexity to
.
This is a joint work with Abdoulaye Maiga.