9 Computing powers of polynomials
This chapter covers
- Exponentiation by expansion of an integer
- A square and multiply algorithm to compute powers of polynomials
- Examples for arbitrary powers of polynomials
- Examples for field prime powers of polynomials
In this chapter, we use the code from chapters 7 and 8 to compute exponentials of polynomials modulo a prime polynomial. These routines are important for computing elliptic curve point pairings that underlie the routines shown in chapters 18 and 19.
Now that we know how to multiply polynomials modulo a prime polynomial, we can compute powers of polynomials. We need this ability to find irreducible polynomials and to find pairing-friendly curves. In chapter 8, we found that powers of a variable modulo the irreducible polynomial are limited to one less than the degree of the irreducible polynomial.
Similar to how we used the double and add method to compute multiplication of a point on an elliptic curve, we are going to use the square and multiply method to compute powers of a polynomial modulo a prime polynomial. This is exponentially faster than the method used in chapter 8.
The next interesting step after computing a general power is to take \(x^p\) modulo the irreducible polynomial where \(p\) is the field prime. This will eventually connect back to the field extension when we compute \(x^{p^j}\).