Skip to main content

Standard curve database

Search

Barreto-Naehrig curves

A class of pairing-friendly curves with embedding degree k=12k = 12. Given an integer zNz \in \mathbb{N} the BN curve with embedding degree 1212 can be constructed over a prime field Fp\mathbb{F}_p with the number of points rr and a trace of Frobenius tt.

p(z)=36z4+36z3+24z2+6z+1r(z)=36z4+36z3+18z2+6z+1t(z)=6z2+1\begin{aligned} p(z) &= 36 z^4 + 36 z^3 + 24 z^2 + 6 z + 1\\ r(z) &= 36 z^4 + 36 z^3 + 18 z^2 + 6 z + 1\\ t(z) &= 6 z^2 + 1 \end{aligned}

The class of curves has the Short-Weierstrass form:

y2x3+by^2 \equiv x^3 + b

where given zz such that p(z)p(z) is prime, a curve with a prime order subgroup of r(z)r(z) points can be found either via complex multiplication or by exhaustively trying small coefficients bb 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 1212.

class BN(object):
@staticmethod
def generate_prime_order(zbits):
while True:
z = randint(2^(zbits - 1), 2^zbits)
pz = int(BN.p(z))
if not is_prime(pz):
continue
rz = int(BN.r(z))
if not is_prime(rz):
continue
break
K = GF(pz)
b = 1
while True:
curve = EllipticCurve(K, [0, b])
card = curve.cardinality()
if card % rz == 0:
break
b += 1
return curve
@staticmethod
def p(z):
return 36 * z^4 + 36 * z^3 + 24 * z^2 + 6 * z + 1
@staticmethod
def r(z):
return 36 * z^4 + 36 * z^3 + 18 * z^2 + 6 * z + 1
@staticmethod
def t(z):
return 6 * z^2 + 1

References

© 2020 Jan Jancar | Built with Dox theme for Gatsby