On the near prime-order MNT curves
Published in Applicable Algebra in Engineering, Communication and Computing, 2018
Recommended citation: Duc-Phong Le, Nadia El Mrabet, Safia Haloui, Chik How Tan. (2019). "On the near prime-order MNT curves." Applicable Algebra in Engineering, Communication and Computing. 30(2). https://link.springer.com/article/10.1007/s00200-018-0363-1
In their seminar paper, Miyaji, Nakabayashi and Takano introduced the first method to construct families of prime-order elliptic curves with small embedding degrees, namely k=3,4, and 6. These curves, so-called MNT curves, were then extended by Scott and Barreto, and also Galbraith, McKee and Valença to near prime-order curves with the same embedding degrees. In this paper, we extend the method of Scott and Barreto to introduce an explicit and simple algorithm that is able to generate all families of MNT curves with any given cofactor. Furthermore, we analyze the number of potential families of these curves that could be obtained for a given embedding degree k and a cofactor h. We then discuss the generalized Pell equations that allow us to construct particular curves. Finally, we provide statistics of the near prime-order MNT curves.
Recommended citation: Duc-Phong Le, Nadia El Mrabet, Safia Haloui, Chik How Tan (2019). “On the near prime-order MNT curves” Applicable Algebra in Engineering, Communication and Computing. 30(2)