How to compute the square root of a polynomial modulo another polynomial?

Question

What is a method to find the polynomial square root modulo another polynomial, i.e. find a polynomial $r(x)$ such that

$$r(x)^2 \mod{x^3+3x+1} = -453600x^2 - 160650x - 4725$$

?

From various sources, this seems to be a computationally hard problem?

1. https://www.youtube.com/watch?v=GcJImruRSyE&t=844s

2. Finding the square root of a ring element modulo a polynomial

3. Does every polynomial over a finite field have a square root modulo an irreducible polynomial?

4. https://www.researchgate.net/publication/242923202_Short_Polynomial_Representations_for_Square_Roots_Modulo_p

Answer 1

Well, it suffices to consider degree $\leq$ 2 polynomials of the form $r(x)=ax^2+bx+c$ since anything larger can be reduced first.

Squaring $r$, reducing $\mod x^3+3x+1$, and equating your polynomial gives $3$ degree $2$ equations in $3$ variables. This can be reduced to a degree $8$ single variable polynomial through substitution which can be solved through numerical approximation (this is known as intersecting $3$ quadrics). This all isn’t computationally expensive (at least when you’re modding a degree 3 polynomial, it’s exponential in the degree), but it seems tricky to explicitly code up.