The embedding degree is the smallest positive integer k for which a large prime subgroup order r satisfies p^k ≡ 1 mod r. It determines how far a prime field must be extended, from p to p^k, before pairing computations can use the required subgroup structure. A base-field curve is G1; the corresponding extension-field curve is G2, using the same curve coefficients while x and y become polynomial values. section 13.1
Figure 13.1 Expanding a prime base field \(p\) to an extension field \(p^k\). Extension fields are required to compute pairings.
The diagram makes the operational move visible: pairing work expands a prime base field p into an extension field p^k. section 13.1
For a curve E over p, start with #E = p + 1 − t, where t is the trace of Frobenius. Over degree k, compute the extension-curve cardinality as #E_k = p^k + 1 − t_k. The traces can be generated from t_0 = 2 and t_1 = p + 1 − #E using t_(n+2) = t_1t_(n+1) − pt_n. These quantities connect the chosen field, curve order, and extension degree. section 13.1
Embedding degree matters because it balances pairing feasibility against security:
- An arbitrary curve with a large prime factor r commonly has an embedding degree on the order of r, making its extension-field representation impractically large for pairings. section 13.1
- Pairing-oriented parameters seek much smaller k values; the cited security-size table associates higher security levels with progressively larger extension fields and embedding-degree ranges. section 14.1
- Curve-search constructions treat k as an input and derive candidate subgroup primes r(z), traces t(z), and field primes q(z), then retain cases where r and q are prime. section 14.2 section 14.5.1
- Very low embedding degree is undesirable for ordinary cryptographic curves, while pairing-friendly curves deliberately search for low-degree extensions. section 6.5 section 14.2
Toy curve with k = 2
A tiny pairing example uses p = 43 and a curve of cardinality 55. Its large prime subgroup factor is r = 11, and its embedding degree is 2. The extension-field group structure is given as 11 × 165. Separately, 41^4 ≡ 1 mod 29 demonstrates an embedding degree of 4 for subgroup order 29. section 13.3 section 13.4
A practical sweep fixes an allowed k and square-free α, sets z = αx², and evaluates construction-specific formulas for r(z), q(z), and t(z). It scans odd x values up to a bound based on the target bit length of r, tests r and q for primality, and reports candidates with their bit sizes, ρ ratio, and trace. The separation between sweeping parameters and constructing a curve keeps the search workflow explicit. section 14.2 section 14.5.1
