7 Description of finite field polynomial math
This chapter covers
- Essence of field extension is a polynomial
- Routines to create polynomials
- An addition routine for polynomials
- A debugging routine for polynomials
In this chapter, I’ll show a simple structure for polynomials and how to add them together. The code developed here is used throughout the rest of the book. Understanding how pairings work on elliptic curves requires the use of field extensions. For an in-depth understanding of field extensions, take a look at chapter 1, section 4 of Lidl and Niederreiter (1997). These are polynomials with finite field coefficients. But they have all the properties of a finite field because there is a fixed number of elements, and they can be added, multiplied, and inverted. The following six chapters are short, so they cover just one aspect of an operation over a field extension. The code to execute the mathematics takes up more text than the mathematical description. Hopefully, it can be easily absorbed so that the code and math associated with elliptic curve pairing operations will then make more sense.
In this chapter, I will cover a polynomial structure, which is much simpler than those used in most mathematics packages. Typical use will be a fixed-sized polynomial, so a general construction is not necessary. A few utility subroutines will be described, along with the addition and subtraction routines.