11 Creating irreducible polynomials
This chapter covers
- Finding irreducible polynomials
- Code for finding irreducible polynomials
Computing pairings of points on elliptic curves over field extensions requires an irreducible polynomial. The irreducible polynomial defines the specific values of the field extension. In this chapter, the details of how to create an irreducible polynomial are described.
In chapter 8, I defined an irreducible polynomial over a finite field as a polynomial with coefficients taken modulo a prime number, which has no other factors. A field extension of degree \(k\) will have a defining irreducible polynomial of degree \(k\). There are a great many irreducible polynomials one can choose to define a field extension. The simplest polynomial with the highest probability of existence is the trinomial (a three-term polynomial) for any field prime. I’ll first describe the theory for finding irreducible trinomials and then explain the code for finding irreducible trinomials.
11.1 Basic theory of irreducible polynomials
In this section, I’ll cover the theory behind the construction of irreducible polynomials. It’s actually more like discovering because the process involves trial and error. I’ll discuss a few theorems that we can take advantage of and then explain an algorithm that will find irreducible polynomials we can use.