**Factoring Polynomials for Constructing Pairing-friendly Elliptic Curves**

*Zhitu su, Hui Li and Jianfeng Ma*

**Abstract: **In this paper we present a new method to construct a polynomial
$u(x) \in \mathbb{Z}[x]$ which will make $\mathrm{\Phi}_{k}(u(x))$
reducible. We construct a finite separable extension of
$\mathbb{Q}(\zeta_{k})$, denoted as $\mathbb{E}$. By primitive
element theorem, there exists a primitive element $\theta \in
\mathbb{E}$ such that $\mathbb{E}=\mathbb{Q}(\theta)$. We represent
the primitive $k$-th root of unity $\zeta_{k}$ by $\theta$ and get a
polynomial $u(x) \in \mathbb{Q}[x]$ from the representation. The
resulting $u(x)$ will make $\mathrm{\Phi}_{k}(u(x))$ factorable.

**Category / Keywords: **public-key cryptography / pairing-friendly curves, polynomial factoring, primitive element theorem

**Date: **received 6 Jan 2008, last revised 12 May 2008

**Contact author: **ztsu at mail xidian edu cn

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20080513:030253 (All versions of this report)

**Short URL: **ia.cr/2008/008

[ Cryptology ePrint archive ]