Complex multiplication (CM) constructs an elliptic curve matching selected pairing parameters. After choosing an embedding degree, field prime, subgroup order, and curve cardinality, CM searches for a compatible curve equation through its j-invariant. section 14.1
The simplified CM workflow connects number-theoretic values to curve coefficients:
- Use the discriminant relation D y² = 4q − t², with q as the field prime and t as the Frobenius trace. section 14.1
- Use the discriminant to define a Hilbert class polynomial, then factor it to obtain candidate j-invariants. section 14.7
- Recover curve coefficients from a j-invariant, test the resulting curve or its twist, and verify its cardinality. section 14.7
- Repeat candidate values because low-embedding-degree algorithms have a low probability of producing acceptable parameters. section 14.7
Pairing parameter targets
For a 128-bit security target, the parameter table lists a 256-bit subgroup, a 3000–5000-bit extension field, and embedding degrees from 12 to 20. section 14.1
Table 14.1 Elliptic curve field sizes for pairings
| Security level | Subgroup size | Extension field | Embedding degree |
|---|---|---|---|
| 80 | 160 | 960–1280 | 6–8 |
| 112 | 224 | 2200–3600 | 10–16 |
| 128 | 256 | 3000–5000 | 12–20 |
| 192 | 384 | 8000–10000 | 20–26 |
| 256 | 512 | 14000–18000 | 28–36 |
Compare subgroup sizes, extension-field sizes, and embedding-degree ranges across security levels before selecting CM parameters. section 14.1
