Factorization of polynomials over finite fields: Difference between revisions

Revision as of 19:11, 6 July 2018

Revision as of 20:54, 8 July 2018

Line 58:

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

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

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

''R'' ← 1

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

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

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

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

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

Line 75 ⟶ 74:

''w'' ← ''y''; ''c'' ← ''c''/''y''; ''i'' ← ''i+1''

'''end while'''

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

# Step 2.: Identify all remaining factors using recursion.

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

'''if''' ''c'' ≠ 1 '''then'''

''c'' ← ''c''^1/''p''

Line 86 ⟶ 85:

'''Output'''(''R'')

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 identifyidentifies the remaining factors,. asAs all of the remaining factors have multiplicity divisible by ''p'', meaning they are powers of ''p'', one can simply take the ''p''-th square root and apply recursion.

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