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“.
Christophe Ritzenthaler, Professor, Université Rennes 1
Fréderik Vercauteren, Associate Professor, KU Leuven
Magali Bardet, Associate Professor, Université de Rouen
Elisa Gorla, Professor, Université de Neuchatel
Guillaume Hanrot, Professor, ÉNS Lyon
Pierrick Gaudry, Senior Research Scientist CNRS, Nancy
Pierre-Jean Spaenlehauer, Research Scientist Inria, Nancy
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.