Finding Good Random Elliptic Curves for Cryptosystems Defined Over $GF(2^n)$
Résumé
One of the main difficulties for implementing cryptographic schemes
based on elliptic curves defined over finite fields is the necessary
computation of the cardinality of these curves. In the case of
finite fields $GF(2^n)$, recent theoretical breakthroughs yield a
significant speed up of the computations. Once described some of
these ideas in the first part of this paper, we show that our
current implementation runs from 2 up to 10 times faster than what
was done previously. In the second part, we exhibit a slight change
of Schoof's algorithm to choose curves with a number of points
``nearly'' prime and so construct cryptosystems based on random
elliptic curves instead of specific curves as it used to be.