Reynald Lercier

R. Lercier. Algorithmique des Courbes Elliptiques dans les Corps Finis. PhD thesis, École polytechnique, Palaiseau, June 1997. In french.

This thesis deals with computations of cardinality of elliptic curves which are defined over a finite field. In a first part, we study Schoof's algorithm and variants due to Atkin and Elkies. We show how these algorithms, initially designed for finite fields of large characteristic, can be applied to fields of small characteristic.

It turns out that most of Atkin's and Elkies' ideas can be used in the last case, except for computing isogenies between elliptic curves. We therefore study five algorithms for computing isogenies in the second part. First algorithm is Atkin's original algorithm for fields of large characteristic. Second and the third are Couveignes's algorithms for finite fields of small characteristic. Finally, we propose a fourth algorithm specially designed for finite fields of characteristic two, and we show in fifth algorithm, how we can extend these ideas for finite fields of odd characteristic p and isogenies of degree l smaller than 2p.

From a practical point of view, we explain how we have programmed the previous algorithms in a third part. In particular, we introduce ZEN, a programming library written in C-language which efficiently computes in every finite extension over a finite ring. Then, we explain how we used the obtained program for efficiently computing number of points of curves defined over any finite fields whose number of points is smaller than 10¹⁰⁰. Moreover, we describe how we can find elliptic curves with good cryptographic properties.

[ bib | preprint | publication ] Back