**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.