A class of pairing-friendly curves with embedding degree . Given an integer the BN curve with embedding degree can be constructed over a prime field with the number of points and a trace of Frobenius .
The class of curves has the Short-Weierstrass form:
where given such that is prime, a curve with a prime order subgroup of points can be found either via complex multiplication or by exhaustively trying small coefficients until a curve is found. Some generated curves can be found in the BN category.
The following SageMath code generates BN curves with embedding degree .
class BN(object):@staticmethoddef generate_prime_order(zbits):while True:z = randint(2^(zbits - 1), 2^zbits)pz = int(BN.p(z))if not is_prime(pz):continuerz = int(BN.r(z))if not is_prime(rz):continuebreakK = GF(pz)b = 1while True:curve = EllipticCurve(K, [0, b])card = curve.cardinality()if card % rz == 0:breakb += 1return curve@staticmethoddef p(z):return 36 * z^4 + 36 * z^3 + 24 * z^2 + 6 * z + 1@staticmethoddef r(z):return 36 * z^4 + 36 * z^3 + 18 * z^2 + 6 * z + 1@staticmethoddef t(z):return 6 * z^2 + 1
- Paulo S. L. M. Barreto, Michael Naehrig: Pairing-Friendly Elliptic Curves of Prime Order
- Geovandro C. C. F. Pereira, Marcos A. Simplício Jr., Michael Naehrig, Paulo S. L. M. Barreto: A Family of Implementation-Friendly BN Elliptic Curves
- Diego F. Aranha, Laura Fuentes-Castaneda, Edward Knapp, Alfred Menezes, Francisco Rodríguez-Henríquez: Implementing Pairings at the 192-bit Security Level