Paper 2008/202

Polynomials for Ate Pairing and ${\mathbf{Ate}}_i$ Pairing

Zhitu Su, Hui Li, and JianFeng Ma

Abstract

The irreducible factor $r(x)$ of ${\mathrm{\Phi }}_k(u(x))$ and $u(x)$ are often used in constructing pairing-friendly curves. $u(x)$ and $u_c\equiv u(x{)}^c(\mathrm{mod}r(x))$ are selected to be the Miller loop control polynomial in Ate pairing and ${\mathrm{Ate}}_i$ pairing. In this paper we show that when $4|k$ or the minimal prime which divides $k$ is larger than $2$, some $u(x)$ and $r(x)$ can not be used as curve generation parameters if we want $$ pairing to be efficient. We also show that the Miller loop length can not reach the bound $$ when we use the factorization of $$ to generate elliptic curves.