On the near prime-order MNT curves
This work is incremental, providing an extension to known methods for constructing near prime-order elliptic curves in cryptography.
The paper tackles the problem of generating all families of MNT curves with any given cofactor by extending an existing method, resulting in an explicit algorithm and analysis of potential families and statistics for these curves.
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 Valenca 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.