International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Elliptic Curves with Low Embedding Degree

Florian Luca
Igor E. Shparlinski
Search ePrint
Search Google
Abstract: Motivated by the needs of the {\it pairing based cryptography\/}, Miyaji, Nakabayashi and Takano have suggested a construction of so-called MNT elliptic curves with low embedding degree. 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).
  title={Elliptic Curves with Low Embedding Degree},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curves, embedding degree, pairing},
  note={ 13064 received 8 Oct 2005},
  author={Florian Luca and Igor E. Shparlinski},