**Barreto-Naehrig Curve With Fixed Coefficient - Efficiently Constructing Pairing-Friendly Curves -**

*Masaaki Shirase*

**Abstract: **This paper describes a method for constructing Barreto-Naehrig (BN) curves and twists of BN curves that are pairing-friendly and have the embedding degree $12$ by using just primality tests without a complex multiplication (CM) method.
Specifically, this paper explains that the number of points of elliptic curves $y^2=x^3\pm 16$ and $y^2=x^3 \pm 2$ over $\Fp$ is given by 6 polynomials in $z$, $n_0(z),\cdots, n_5(z)$, two of which are irreducible, classified by the value of $z\bmod{12}$ for a prime $p(z)=36z^4+36z^3+24z^2+6z+1$ with $z$ an integer.
For example, elliptic curve $y^2=x^3+2$ over $\Fp$ always becomes a BN curve for any $z$ with $z \equiv 2,11\!\!\!\pmod{12}$.
Let $n_i(z)$ be irreducible.
Then, to construct a pairing-friendly elliptic curve, it is enough to find an integer $z$ of appropriate size such that $p(z)$ and $n_i(z)$ are primes.

**Category / Keywords: **foundations / Pairing-friendly elliptic curve, Barreto-Naehrig curve, twist, Gauss' theorem, Euler's conjecture

**Date: **received 11 Mar 2010, last revised 18 Jun 2010

**Contact author: **shirase at fun ac jp

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

**Version: **20100618:113843 (All versions of this report)

**Short URL: **ia.cr/2010/134

[ Cryptology ePrint archive ]