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 FF be a finite field of order F=q|F| = q, E(F)E(F) an elliptic curve over FF, and let rr be a prime factor of the order nn of E(F)E(F). The embedding degree of E(F)E(F) with respect to rr is the smallest integer kk such that the following equation holds:

rqk1.r | q^k − 1.

Fermat’s little theorem implies that there always exists an embedding degree k(r)k(r) for every elliptic curve and that any factor rr of the curve’s order nn, since k=r1k = r − 1 is always a solution to the congruency qk1modrq^k ≡ 1 \mod r. This implies that the remainder of the integer division of qr11q^{r−1} − 1 by rr is 00.

Notation: Let FF be a finite field of order qq, and be E(F)E(F) an elliptic curve over FF such that rr is a prime factor of the order of E(F)E(F). We write k(r)k(r) for the embedding degree of E(F)E(F) with respect to rr.

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 2,4,62, 4, 6 or 1212, and the number rr is the largest prime factor of the curve’s order.

Examples:

  • Bn254 (alt_bn128): r=21888242871839275222246405745257275088548364400416034343698204186575808495617k(r)=12r = 2188824287183927522224640574525727508854836440041 6034343698204186575808495617 \\ k(r) = 12

  • secp256k1: r=115792089237316195423570985008687907852837564279074904382605163141518161494337k(r)=192986815395526992372618308347813175472927379845817397100860523586360249056r = 1157920892373161954235709850086879078528375642790 74904382605163141518161494337 \\ k(r) = 192986815395526992372618308347813175472927379845817397100860523586360249056

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