MNT Elliptic Curves with Non-Prime Order

Miyaji, Nakabayashi, and Takano proposed the algorithm for the construction of prime order pairing-friendly elliptic curves with embedding degrees $k=3,4,6$. We present a method for generating generalized MNT curves. The order of such pairing-friendly curves is the product of two prime numbers.