Elliptic Curves with Low Embedding Degree

Miyaji, Nakabayashi and Takano have recently suggested a construction of the so-called MNT elliptic curves with low embedding degree, which are also of importance for pairing-based cryptography. We give some heuristic arguments which suggest that there are only about z^{1/2+ o(1)} of MNT curves with complex multiplication discriminant up to z. We also show that there are very few finite fields over which elliptic curves with small embedding degree and small complex multiplication discriminant may exist (regardless of the way they are constructed).

Authors and Affiliations

1. Instituto de Matematicas, Universidad Nacional Autonoma de Mexico, C.P. 58089, Morelia, Michoacan, Mexico

   Florian Luca

2. Department of Computing, Macquarie University, Sydney, NSW 2109, Australia

   Igor E. Shparlinski

Corresponding authors

Correspondence to Florian Luca or Igor E. Shparlinski.

Reprints and permissions