**Construction of Pairing-Friendly Elliptic Curves**

*Woo Sug Kang*

**Abstract: **We explain a method of finding the polynomials representing $\sqrt{-D}$ and $\zeta_k$ over the field containing $\sqrt{-D}$ and $\zeta_k$ and how to construct a pairing friendly elliptic curves over the cyclotomic fields containing ${\mathbb Q} (\zeta_k, \sqrt{-D})$ for arbitrary $k$ and $D$ by CP method. By using the factorization of the cyclotomic polynomial combined some polynomial, we extend the construction over cyclotomic fields to the construction over some extensions of the cyclotomic fields containing ${\mathbb Q} (\zeta_k, \sqrt{-D})$. We explain the limitation of finding more families of pairing friendly elliptic curves with embedding degree 10. For all computation, we use the PARI-GP \cite{GP}.

**Category / Keywords: **implementation / elliptic curves, embedding degree, pairing based cryptography

**Date: **received 23 Mar 2007, last revised 18 May 2007

**Contact author: **wsgkang at korea ac kr

**Available format(s): **PDF | BibTeX Citation

**Version: **20070518:120843 (All versions of this report)

**Short URL: **ia.cr/2007/110

[ Cryptology ePrint archive ]