We give an upper bound on the number of finite fields over which elliptic curves of cryptographic interest with a given embedding degree and small complex multiplication discriminant may exist, and present some heuristic arguments which indicate that this bound is tight. We also refine some heuristic arguments on the total number of so-called MNT curves with prime cardinalities which have been recently presented by various authors.
Copyright 2011 American Mathematical Society. First published in Mathematics of computation, Vol. 81, No. 278, pp.1093-1110, published by the American Mathematical Society. The original article can be found at http://dx.doi.org/10.1090/S0025-5718-2011-02543-3