Place : LIX, Salle Nicole-Reine Lepaute.
Title: Counting points on hyperelliptic curves defined over finite fields of
large characteristic: algorithms and complexity.
Abstract:
Counting points on algebraic curves has drawn a lot of attention due to its
many applications from number theory and arithmetic geometry to cryptography
and coding theory. In this talk, we focus on counting points on hyperelliptic
curves over finite fields of large characteristic p. In this setting, the most
suitable algorithms are currently those of Schoof and Pila, because their
complexities are polynomial in log p. However, their dependency in the genus g
of the curve is exponential, and this is already painful even in genus 3.
Our contributions mainly consist of establishing new complexity bounds with a
smaller dependency in g of the exponent of log p. For hyperelliptic curves,
previous work showed that it was quasi-quadratic, and we reduced it to a linear
dependency. Restricting to more special families of hyperelliptic curves with
explicit real multiplication (RM), we obtained a constant bound for this
exponent.
In genus 3, we proposed an algorithm based on those of Schoof and
Gaudry-Harley-Schost whose complexity is prohibitive in general, but turns out
to be reasonable when the input curves have explicit RM. In this more favorable
case, we were able to count points on a hyperelliptic curve defined over a
64-bit prime field.
In this talk, we will carefully reduce the problem of counting points to that
of solving polynomial systems. More precisely, we will see how our results are
obtained by considering either smaller or structured systems.
Contains joint work with P. Gaudry and P.-J. Spaenlehauer.
