Paper 2010/134
BarretoNaehrig Curve With Fixed Coefficient  Efficiently Constructing PairingFriendly Curves 
Masaaki Shirase
Abstract
This paper describes a method for constructing BarretoNaehrig (BN) curves and twists of BN curves that are pairingfriendly 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 pairingfriendly elliptic curve, it is enough to find an integer $z$ of appropriate size such that $p(z)$ and $n_i(z)$ are primes.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Pairingfriendly elliptic curveBarretoNaehrig curvetwistGauss' theoremEuler's conjecture
 Contact author(s)
 shirase @ fun ac jp
 History
 20100618: last of 2 revisions
 20100312: received
 See all versions
 Short URL
 https://ia.cr/2010/134
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/134, author = {Masaaki Shirase}, title = {BarretoNaehrig Curve With Fixed Coefficient  Efficiently Constructing PairingFriendly Curves }, howpublished = {Cryptology {ePrint} Archive, Paper 2010/134}, year = {2010}, url = {https://eprint.iacr.org/2010/134} }