  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.

Cryptography and Security