14 Finding low embedding degree elliptic curves
This chapter covers
- Algorithms for finding low embedding degree field extensions
- The \(j\)-invariant and Hilbert class polynomials
- The method of complex multiplication, used to find elliptic curves
- Routines to find secure curves with low embedding degree
In this chapter, I’ll explain the reasons for choosing a specific size of extension field to create a secure pairing-friendly curve. The optimal size depends on the security level desired—too small and it might be broken; too large and it may not be efficient for practical use. I then discuss algorithms that can find curves of a low embedding degree. This involves searching for primes using mathematical functions. The parameters found during this process will allow us to use another mathematical function to find curves that have the prime number of points found for pairings.
The method used to find the curves of interest is called complex multiplication. One of the parameters from the search process will tell us which function we use to find the curve coefficients. The factoring of that function is the last step in theory before diving into code.