8 Multiplication of polynomials explained
This chapter covers
- Irreducible polynomials
- How irreducible polynomials act like primes
- Multiplying two polynomials modulo an irreducible polynomial
In this chapter, we’ll learn what irreducible polynomials are and how they depend on the underlying prime number modulus. The fundamental takeaway for this chapter is the multiplication table derived from an irreducible polynomial that defines an extension field. This table will allow us to compute extension field algorithms efficiently. The code for this chapter is the core of all the routines in the rest of the book.
As I said in chapter 7, I left out some details about finite field extensions. The first detail is that the arbitrary symbol \(x\) or \(t\) is not actually arbitrary. It is the solution to an irreducible polynomial equation. In this chapter, we dive into the detail of what makes a polynomial irreducible and how that is used like a prime number to create finite fields over polynomials.
The coefficients are reduced modulo a field prime, as shown in chapter 7, but the multiplication of two polynomials requires a modulus that is a polynomial. I will sometimes use the term prime polynomial instead of irreducible polynomial. The difference in terminology comes from the use of the polynomial as a modulus, where it is like a prime versus its use as a factor where it is irreducible.