12 Taking square roots of polynomials
This chapter covers
- Polynomial pseudo-division
- Resultant function of two polynomials
- Quadratic residue for a polynomial
- Square root of a polynomial modulo a prime polynomial
In this chapter, we’ll dive into the details of computing square roots modulo a prime polynomial so we can find solutions to the elliptic curve equation. At the end of chapter 2, I showed you how to compute square roots over a prime number field. The same process is used over a field created by an irreducible polynomial.
The equation of an elliptic curve has the form \(y^2=f(x)\). The example given in chapter 3 is \(y^2=x^3-5 x +5\), where \(f(x) = x^3-5x+5\). To find the \(y\) coordinate requires taking a square root. When the field we are using is an extension of a prime field, the coordinates are polynomials.
Computing square roots modulo an irreducible polynomial is similar to computing square roots modulo a prime number. The main difference is that we are looking for two identical polynomial factors. This is similar to factoring a polynomial.
In the article by Doliskani and Schost (2011), there are descriptions of algorithms for exceptionally high polynomial degrees. They show that the algorithm of Tonelli-Shanks is perfectly adequate for our purposes since our embedding degrees are small. This is fortunate because we already know how to perform the Tonelli-Shanks algorithm with prime numbers.