Factorization of polynomials over finite fields: Difference between revisions

Revision as of 17:17, 16 May 2018

Revision as of 19:11, 6 July 2018

Line 56:

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 compute first 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''.

'''Algorithm''': '''SFF''' (Square-Free Factorization)

'''Input''': A [[monic polynomial]] ''f'' in '''F'''_''q''[''x''] where ''q=p^m''

'''Output''': Square-free factorization of ''f;''

''wR'' ← ''f''/''c''1

''i''←1; ''R'' ← 1; ''g'' ← ''f''′;

# Make ''w'' contain the product (without multiplicity) of all factors of ''f'' that have

'''if''' ''g'' ≠ 0 '''then'''

# multiplicity not divisible by ''p''. If m>1 then some factors with multiplicity

''c'' ← '''gcd'''(''f'', ''g'')

# divisible by ''p'' might also tag along (without their multiplicity).

''w'' ← ''f''/''c''

''c'' ← '''whilegcd''' (''wf'' ≠ 1, ''f'do''' ′)

''yw'' ← ''f'gcd'''(''w'', /''c''); ''z'' ← ''w''/''y''

''R'' ← ''R''·''z''^''i''; ''i'' ← i+1

# Step 1: Identify all factors in ''w''

''w'' ← ''y''; ''c'' ← ''c''/''y''

''i'end'←1 while'''

'''ifwhile''' ''cw'' ≠ 1 '''thendo'''

''cy'' ← ''c'gcd'^{1/''p(''w'', ''c''})

''fac'Output' ← ''(w''R/''·y'''SFF'''(''c'')^''p'')

''R'else' ← '' R''·''fac''^''i''

''w'' ← ''y'Output'; ''(c''R ← '')c''/''y''; ''i'' ← ''i+1''

'''end ifwhile'''

# ''c'' is now the product (with multiplicity) of the remaining factors of ''f''.

'''else'''

''f'' ← ''f''^1/''p''

# Step 2. Identify all remaining factors using recursion.

'''Output'''('''SFF'''(''f'')^''p'')

# Note that the factors will have multiplicity divisible by p.

'''end if'''

'''if''' ''gc'' ≠ 01 '''then'''

''i''←1; ''Rc'' ← 1; ''gc'' ← ^{1/''fp''′;}

The test "'''if''' ''g'' ≠ 0" and its else clause are not needed, as, if {{nowrap|1=''f''{{space|hair}}′ = 0}}, one has ''w'' = 1 and {{nowrap|1=''c'' = ''f'' ≠ 1}}, and the case is correctly handled by the test {{nowrap|"'''if''' ''c'' ≠ 1"}}. Nevertheless the test "'''if''' ''g'' ≠ 0" has been kept as being not costly and possibly clearer for some readers.

''cR'' ← ''R'gcd'·''('SFF'f'', (''gc'')^''p''

'''elseend if'''

'''Output'''(''R'SFF'''(''f'')^''p'')

The idea is to identify the product of all irreducible factors of ''f'' with the same multiplicity. This is done in two steps. The first step uses the formal derivative of ''f'' to find all the factors with multiplicity not divisible by ''p'', in the case of ''m>1'' it might also find some additional factors. The second step is to identify the remaining factors, as all the remaining factors are powers of ''p'' one can simply take the ''p''-th square root and apply recursion.

====Example of a square-free factorization====