Simon Abelard will defend his thesis on Friday, September 7th at 2.30pm in room C005.

His presentation is entitled “Point-counting on hyperelliptic curves defined over finite fields of large characteristic: algorithms and complexities“.

Referees:
Christophe Ritzenthaler, Professor, Université Rennes 1
Fréderik Vercauteren, Associate Professor, KU Leuven

Examiners:
Magali Bardet, Associate Professor, Université de Rouen
Elisa Gorla, Professor, Université de Neuchatel
Guillaume Hanrot, Professor, ÉNS Lyon

Advisors:
Pierrick Gaudry, Senior Research Scientist CNRS, Nancy
Pierre-Jean Spaenlehauer, Research Scientist Inria, Nancy

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 thesis, 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.