10 Description of polynomial division using Euclid’s algorithm
This chapter covers
- Quotient and remainder from Euclid’s algorithm
- Greatest common divisor of polynomials
- Inversion modulo an irreducible polynomial
In this chapter, I’ll cover polynomial division, which is required to compute the point addition algorithm for points on a field extension elliptic curve. To compute elliptic curve formulas over finite fields consisting of polynomials, we started in chapters 7 to 9 working with polynomials performing addition and multiplication. In this chapter, we are going to dive into division so we can compute slopes of lines in an extension field. Working with an irreducible polynomial is similar to working with a prime number in terms of fields. Inversion modulo an irreducible polynomial is similar to inversion modulo a prime number. I’ll also cover Euclid’s division algorithm applied to polynomials. Using that algorithm, I’ll then look at the greatest common divisor function. The greatest common divisor (gcd) of polynomials will be used to help us find irreducible polynomials in chapter 11.
The last algorithm of this chapter covers inversion modulo a prime polynomial. Inversion is really the extended Euclidean algorithm, but we don’t need the quotient portion. I then show that division of two polynomials modulo an irreducible polynomial is inversion followed by multiplication.