Cryptology ePrint Archive: Report 2015/835

On near prime-order elliptic curves with small embedding degrees (Full version)

Duc-Phong Le and Nadia El Mrabet and Chik How Tan

Abstract: In this paper, we extend the method of Scott and Barreto and present an explicit and simple algorithm to generate families of generalized MNT elliptic curves. Our algorithm allows us to obtain all families of generalized MNT curves with any given cofactor. Then, we analyze the complex multiplication equations of these families of curves and transform them into generalized Pell equation. As an example, we describe a way to generate Edwards curves with embedding degree 6, that is, elliptic curves having cofactor h = 4.

Category / Keywords: Pairing Friendly Elliptic Curve, MNT curves, Complex Multiplication, Pell's equation.

Original Publication (with minor differences): 6th International Conference on Algebraic Informatics, CAI 2015

Date: received 28 Aug 2015, last revised 7 Mar 2016

Contact author: tslld at nus edu sg

Available format(s): PDF | BibTeX Citation

Note: Small changes at title and references.

Version: 20160308:063014 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]