Barreto-Naehrig Curve With Fixed Coefficient - Efficiently Constructing Pairing-Friendly Curves -.
Masaaki Shirase · 2010
Abstract. This paper describes a method for constructing Barreto-Naehrig curves that are pairing-friendly and have the embedding de-gree 12 having fixed coefficients, by using just primality tests without the complex multiplication method. Moreover, this paper discusses their twists. Specifically, this paper explains that the number of points on el-liptic curves y2 = x3 ± 16 and y2 = x3 ± 2 over Fp(z) is given by one of 6 polynomials in z, n0(z), · · · , n5(z), classified by the value of z mod 12 for a prime p(z) = 36z4+36z3+24z2+6z+1 with z an integer. The polyno-mial n5(z) represents the number of points on BN curves. For example, elliptic curve y2 = x3 + 2 over Fp(z) always becomes a BN curve for any integer z with z ≡ 2, 11 (mod 12). Then, to construct a pairing-friendly elliptic curve, it is enough to find an integer z of appropriate size such that p(z) and n5(z) are primes.