Skip to Main content Skip to Navigation
Theses

Algorithmique des courbes elliptiques dans les corps finis

Abstract : 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^100. Moreover, we describe how we can find elliptic curves with good cryptographic properties.
Keywords : Elliptic curve
Document type :
Theses
Complete list of metadatas

Cited literature [111 references]  Display  Hide  Download

https://hal-univ-rennes1.archives-ouvertes.fr/tel-01101949
Contributor : Reynald Lercier <>
Submitted on : Saturday, January 10, 2015 - 8:02:20 PM
Last modification on : Friday, July 10, 2020 - 4:05:12 PM
Long-term archiving on: : Monday, April 13, 2015 - 5:08:53 AM

Identifiers

  • HAL Id : tel-01101949, version 1

Citation

Reynald Lercier. Algorithmique des courbes elliptiques dans les corps finis. Informatique [cs]. Ecole Polytechnique, 1997. Français. ⟨tel-01101949⟩

Share

Metrics

Record views

986

Files downloads

1236