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.

12.1 Mathematics for square root modulo a prime polynomial

12.2 Code for square roots modulo a prime polynomial

12.2.1 Content routine

12.2.2 Pseudo-division routine

12.2.3 Resultant subroutine

12.2.4 Quadratic residue

12.2.5 Polynomial square root routine

Answer to exercise

Summary