Factorization of polynomials over finite fields: Difference between revisions

Revision as of 20:43, 20 November 2020

Revision as of 01:44, 8 December 2020

Line 53:

The algorithm determines a [[square-free polynomial|square-free]] factorization for polynomials whose coefficients come from the finite field '''F'''_''q'' of order ''q'' = ''p^m'' with ''p'' a prime. This algorithm firstly determines the [[derivative]] and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields).

This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in ''x''^''p'', which is, if the coefficients belong to '''F'''_''p'', the ''p''th power of the polynomial obtained by substituting ''x'' by ''x''^1/''p''. If the coefficients do not belong to '''F'''_''p'', 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. {{Citation needed}}

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 first computes the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a ''p'' such that they remain square-free modulo ''p''.

Line 100:

:<math> f= (x+1)(x^2+1)^3(x+2)^4.</math>

===Distinct-degree factorization===