Content deleted Content added
→Distinct-degree factorization: fixed set unions and pseudo-code syntax more consistent within page |
m →Distinct-degree factorization: homogenizing notation |
||
Line 106:
'''Algorithm''' Distinct-degree factorization(DDF)
'''Input''': A monic square-free polynomial {{math|''f'' ∈ '''F'''<sub>''q''</sub>[''x'']}}
'''Output''': The set of all pairs {{math|(''g'', ''d'')}}, such that
{{math|''f''}} has an irreducible factor of degree {{math|''d''}} and
{{math|''g''}} is the product of all monic irreducible factors of {{math|''f''}} of degree {{math|''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''' {{math|''g'' ≠ 1}}, '''then'''
<math>S:=S\cup\{(g,i)\}</math>;
'''end if'''
{{math|1=''i'' := ''i'' + 1;}}
'''end while''';
'''if'''
'''if'''
'''else return''' {{math|''S''}}
'''End'''
The correctness of the algorithm is based on the following:
|