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

$$r | q^k − 1.$$

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

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

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, 6$ or $12$, and the number $r$ is the largest prime factor of the curve’s order.

Examples:

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

• secp256k1: $r = 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)