Content deleted Content added
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''.
'''Input''': A [[monic polynomial]] ''f'' in '''F'''<sub>''q''</sub>[''x''] where ''q=p<sup>m</sup>''
'''Output''': Square-free factorization of ''f''
''R'' ← 1
# Make ''w'' be the product (without multiplicity) of all factors of ''f'' that have
# multiplicity not divisible by ''p''
''c'' ← '''gcd'''(''f'', ''f''′)
''w'' ← ''f''/''c''
# Step 1: Identify all factors in ''w''
''i''←1
'''while''' ''w'' ≠ 1 '''do'''
''y'' ← '''gcd'''(''w'', ''c'')
''fac'' ← ''w''/''y''
''R'' ← ''R''·''fac''<sup>''i''</sup>
''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 these are the factors of ''f'' that have multiplicity divisible by ''p''
'''if''' ''c'' ≠ 1 '''then'''
''c'' ← ''c''<sup>1/''p''</sup>
''R'' ← ''R''·'''SFF'''(''c'')<sup>''p''</sup>
'''end if'''
'''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''. The second step identifies the remaining factors. As 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.
Line 104:
This algorithm splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree. Let ''f'' ∈ '''F'''<sub>''q''</sub>[''x''] of degree ''n'' be the polynomial to be factored.
'''Input''': A monic square-free polynomial ''f'' ∈ '''F'''<sub>''q''</sub>[''x'']
'''Output''': The set of all pairs (''g'', ''d''), such that
''f'' has an irreducible factor of degree ''d'' and
''g'' is the product of all monic irreducible factors of ''f'' of degree ''d''.
'''Begin'''
<math>i:=1;\qquad S:=\emptyset,\qquad f^*:=f;</math>
'''while''' <math>\deg f^*\ge 2i</math> '''do'''
<math>g=\gcd(f^*, x^{q^i}-x)</math>
'''if''' ''g'' ≠ 1, '''then'''
<math>S:=S\cup{(g,i)}</math>;
''f*'' := ''f*''/''g'';
'''end if'''
''i'' := ''i''+1;
'''end while''';
'''if''' ''f*'' ≠ 1, '''then''' <math>S:= S\cup{(f^*,\deg f^*)}</math>;
'''if''' ''S'' = ∅
'''then return''' {(''f'', 1)}
'''else return''' ''S''
'''End'''
The correctness of the algorithm is based on the following:
Line 178:
We first describe an algorithm by Cantor and Zassenhaus (1981) and then a variant that has a slightly better complexity. Both are probabilistic algorithms whose running time depends on random choices ([[Las Vegas algorithm]]s), and have a good average running time. In next section we describe an algorithm by Shoup (1990), which is also an equal-degree factorization algorithm, but is deterministic. All these algorithms require an odd order ''q'' for the field of coefficients. For more factorization algorithms see e.g. Knuth's book [[The Art of Computer Programming]] volume 2.
'''Input:''' A finite field '''F'''<sub>''q''</sub> of odd order ''q''.
A monic square free polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'' = ''rd'',
which has ''r'' ≥ 2 irreducible factors each of degree ''d''
'''Output:''' The set of monic irreducible factors of ''f''.
Factors := {''f''};
while Size(Factors) < ''r'' do,
Choose ''h'' in '''F'''<sub>''q''</sub>[''x''] with deg(''h'') < ''n'' at random;
<math>g:=h^{\frac{q^d-1}{2}}- 1 \pmod f</math>
for each ''u'' in Factors with deg(''u'') > ''d'' do
if gcd(''g'', ''u'') ≠ 1 and gcd(''g'', ''u'') ≠ ''u'', then
Factors:= Factors<math>\,\setminus\, \{u\}\cup\{(\gcd(g,u),u/\gcd(g,u))\}</math>;
endif;
endwhile
return Factors.
Line 258 ⟶ 259:
Let ''p''<sub>1</sub>, ..., ''p<sub>k</sub>'', be all the prime divisors of ''n'', and denote <math>n/p_i=n_i</math>, for 1 ≤ ''i'' ≤ ''k'' polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'' is irreducible in '''F'''<sub>''q''</sub>[''x''] if and only if <math> \gcd \left (f,x^{q^{n_i}}-x \right )=1</math>, for 1 ≤ ''i'' ≤ ''k'', and ''f'' divides <math>x^{q^n}-x</math>. In fact, if ''f'' has a factor of degree not dividing ''n'', then ''f'' does not divide <math>x^{q^n}-x</math>; if ''f'' has a factor of degree dividing ''n'', then this factor divides at least one of the <math>x^{q^{n_i}}-x.</math>
'''Input''': A monic polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'',
''p''<sub>1</sub>, ..., ''p<sub>k</sub>'' all distinct prime divisors of ''n''.
'''Output''': Either "''f'' is irreducible" or "''f'' is reducible".
<math>n_j=n/p_j</math>;
<math>h:=x^{q^{n_i}}-x \bmod f</math>;
''g'' := gcd(''f'', ''h'');
'''if''' ''g'' ≠ 1, '''then return''' "''f'' is reducible" '''and STOP''';
The basic idea of this algorithm is to compute <math> x^{q^{n_i}} \bmod f</math> starting from the smallest <math> n_1,\ldots,n_k</math> by repeated squaring or using the [[Finite field#Frobenius automorphisms|Frobenius automorphism]], and then to take the correspondent gcd. Using the elementary polynomial arithmetic, the computation of the matrix of the Frobenius automorphism needs <math>O(n^2 (n+\log q))</math> operations in '''F'''<sub>''q''</sub>, the computation of
| |||