Algorithmique des Courbes
Elliptiques dans les Corps Finis.
PhD thesis, École polytechnique, Palaiseau, June 1997.
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.
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 10100. Moreover, we
describe how we can find elliptic curves with good
[ bib |