View article

Finding suitable elliptic curves for pairing-based cryptosystems is a crucial step for their actual deployment. Miyaji, Nakabayashi and Takano [12] (MNT) were the first to produce ordinary pairing-friendly elliptic curves of prime order with embedding degree . Scott and Barreto [16] as well as Galbraith et al. [10] extended this method by allowing the group order to be non-prime. The advantage of this idea is the construction of much more suitable elliptic curves, which we will call generalized MNT curves. A necessary step for the construction of such elliptic curves is finding the solutions of a generalized Pell equation. However, these equations are not always solvable and this fact considerably affects the efficiency of the curve construction. In this paper we discuss a way to construct generalized MNT curves through Pell equations which are always solvable and thus considerably improve the efficiency of …