Content deleted Content added
→Square-free factorization: Fixed grammar Tags: canned edit summary Mobile edit Mobile app edit Android app edit |
|||
Line 55:
This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in ''x''<sup>''p''</sup>, which is, if the coefficients belong to '''F'''<sub>''p''</sub>, the ''p''th power of the polynomial obtained by substituting ''x'' by ''x''<sup>1/''p''</sup>. If the coefficients do not belong to '''F'''<sub>''p''</sub>, the ''p''-th root of a polynomial with zero derivative is obtained by the same substitution on ''x'', completed by applying the inverse of the [[Frobenius endomorphism|Frobenius automorphism]] to the coefficients.
This algorithm works also over a field of [[characteristic (algebra)|characteristic]] zero, with the only difference that it never enters in the blocks of instructions where ''p''th roots are computed. However, in this case, [[Square-free polynomial#Yun's algorithm|Yun's algorithm]] is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one
'''Algorithm''': '''SFF''' (Square-Free Factorization)
'''Input''': A [[monic polynomial]] ''f'' in '''F'''<sub>''q''</sub>[''x''] where ''q=p<sup>m</sup>''
| |||