Embedding Degrees
Every elliptic curve gives rise to a pairing map. However, not every such pairing can be efficiently computed. In order to distinguish curves with efficiently computable pairings from the rest, we need to start with an introduction to the so-called embedding degree of a curve.
Let be a finite field of order , an elliptic curve over , and let be a prime factor of the order of . The embedding degree of with respect to is the smallest integer such that the following equation holds:
Fermat’s little theorem implies that there always exists an embedding degree for every elliptic curve and that any factor of the curve’s order , since is always a solution to the congruency . This implies that the remainder of the integer division of by is .
Notation: Let be a finite field of order , and be an elliptic curve over such that is a prime factor of the order of . We write for the embedding degree of with respect to .
In real-world applications, like in the case of pairing-friendly elliptic curves such as BLS_12-381
, usually only the embedding degree of the large prime factor is relevant. It should be noted, however, that every prime factor of a curve’s order has its own embedding degree despite the fact that this is mostly irrelevant in applications.
In real-world applications of pairing-friendly elliptic curves, the embedding degree is usually a small number like or , and the number is the largest prime factor of the curve’s order.
Examples:
Bn254 (alt_bn128):
secp256k1:
Sage example:
# Bn254
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
F_p = GF(p)
(a, b) = (0, 3)
E = EllipticCurve(F_p, [a, b])
def embedding_degree(E, r):
for k in range(1, r):
if (p^k - 1) % r == 0:
return k
r = 21888242871839275222246405745257275088548364400416034343698204186575808495617
embedding_degree(E, r)
Last updated