Algorithm for finding the square root of a polynomial...

Solution 1:

It's just saying start with the highest degree and work down. This may not be the fastest but will work or tell you that the thing is not really a square. So, begin with $x^3,$ since the square must be $x^6$ and we get one free choice, $\pm x^3.$ Next, $(x^3 + A x^2)^2 = x^6 + 2 A x^5 + \mbox{more}.$ So $2A = -2, A = -1.$

Alright, $(x^3 -x^2 + B x)^2 = x^6 - 2 x^5 + (2B+1)x^4 + \mbox{more}.$ So $2B+1 = 5$ and $B=2.$

Finally $(x^3 - x^2 + 2 x + C)^2 = x^6 - 2 x^5 + 5 x^4 +(2C -4)x^3 + \mbox{more}.$ So $2C-4 = -6$ and $C=-1.$

Then check $$ (x^3 - x^2 + 2 x -1)^2 = x^6 - 2 x^5 +5 x^4 - 6 x^3 + 6 x^2 - 4 x + 1. $$ So it worked.

Solution 2:

If you know that the polynomial is a perfect square, then the square root algorithm works. For example

$$\sqrt{x^6 - 6x^5 + 17x^4 - 36x^3 + 52x^2 - 48x + 36}$$

\begin{array}{lcccccccccccccc} &&x^3 && -3x^2 && +4x && -6\\ &&---&---&---&---&---&---&---\\ x^3 &|& x^6 & -6x^5 & +17x^4 & -36x^3 & +52x^2 & -48x & +36\\ && x^6\\ &&---&---&---\\ &&& -6x^5 & +17x^4 \\ (2)x^3-3x^2 &|& &-6x^5 &+9x^4\\ &&&---&---&---&---\\ &&&& +8x^4 &-36x^3 &+52x^2\\ (2)x^3-(2)3x^2+ 4x &|&&&+8x^4 &-24x^3 &+16x^2\\ &&&&---&---&---&---&---\\ &&&& &-12x^3 &+36x^2 &-48x &+36\\ (2)x^3-(2)3x^2+ (2)4x - 6&|&&&& -12x^3 &+36x^2 &-48x &+36\\ &&&&&---&---&---&---\\ \end{array}

$\text{STEP}\;1.\qquad$ Compute the square root of the leading term (x^6) and put it, (x^3), in the two $\phantom{\text{STEP}\;1.}\qquad$ places shown.

$\text{STEP}\;2.\qquad$ Subtract and bring down the next two terms.

$\text{STEP}\;3.\qquad$ Double the currently displayed quotient $(x^3 \to (2)x^3)$ Then add a new term, $X$, $\phantom{\text{STEP}\;3.}\qquad$ to the quotient such that $X(2x^3 + X)$ will remove the first term, $(-6x^5)$, in the $\phantom{\text{STEP}\;3.}\qquad$ current partial remainder.

$\text{STEP}\;4.\qquad$ Repeat steps $2$ and $3$ until done.