Talk:Square-free polynomial

[Untitled]

Sometimes people do really weird things with TeX. I found this:

$f_{0}=f\,$, $f_{1}=\gcd(f_{0},f_{0}')\,$, $f_{2}=\gcd(f_{1},f_{1}')\,$, $f_{3}=\gcd(f_{2},f_{2}')\,$, $\dots$

and I changed it to this:

$f_{0}=f,\ f_{1}=\gcd(f_{0},f_{0}'),\ f_{2}=\gcd(f_{1},f_{1}'),\ f_{3}=\gcd(f_{2},f_{2}'),\dots$

The misaligned commas and misaligned final dots wouldn't have happened if TeX had been used properly. Michael Hardy (talk) 00:45, 13 February 2009 (UTC)

Complexity

What is the meaning of the sentence In characteristic zero, their computational complexity is lower than twice that of the computation of the greatest common divisor of the polynomial and its derivative.?

Usually one ignores constant factors when talking about complexity, so can we drop the twice? Then it seems that, at least naively, you need to compute degree many gcds.

Is it obvious that the gcd is provably the dominating factor in the complexity? I.e., how do we know that in this special case, it's not possible to compute the gcd quickly, which make the divisons dominate? [I trust that these gcds are harder, but it's not entirely obvious, is it?]

I changed the wording, feel free to edit it back. Saraedum (talk) 23:28, 9 August 2012 (UTC)

In fact, this assertion on complexity is true only for univariate polynomials and one should include in the computation time of the GCD the time for computing the quotients of the input polynomials by their GCD. I believe that this is the main result of Yun's paper, but not having the paper at hand, I can not verify this immediately. The result follows from the fact that the complexity of GCD is at least linear in the input degree and from the following result: let us call input degree of a GCD computation, the maximal degree of its input. Then the sum of the input degrees of the GCD's that are needed to complete the computation (after having computed the GCD of the polynomial and its derivative) is upper bounded by the degree of the input polynomial. I'll thus revert your edit and correct the assertion. D.Lazard (talk) 10:07, 10 August 2012 (UTC)

square root of a polynomial

Given we are talking about square free polynomial, should we have a link for find the square root of a polynomial, especially for the context of a extended Finite field. Jackzhp (talk) 07:23, 15 January 2018 (UTC)

I have added a section to the article, and updated accordingly the redirect Square root of polynomial. I do not know what is "a extended Finite field". D.Lazard (talk) 08:10, 15 January 2018 (UTC)