Square root of a polynomial

Use single point evaluation to transform the polynomial square root problem into the integer square root problem. Then find the integer square root and use to reconstruct the polynomial .

Create a problem from its solution.

> ans := randpoly(x,degree=9,dense,coeffs=rand(10^8));

> que := sort(expand(ans^2));

Bound the coefficients in the answer.

> L := length(maxnorm(que));

> M := 10^(iquo(L,2)+1);

Convert the polynomial problem to an integer problem.

> queM := subs(x=M,que);

Compute the integer square root. Note that both the input number and the output number to the integer square root procedure contain numbers with more than 16 digits.

> ansM := isqrt(queM);

Check the integer square root.

> check1 := queM-ansM^2;

Convert the integer to a polynomial.

> ans1 := sort(genpoly(ansM,M,x));

Check the answer.

> check2 := ans-ans1;