Content deleted Content added
Plastikspork (talk | contribs) Clean up duplicate template arguments using findargdups |
Small correction (added \cdots in one place) |
||
Line 228:
Let ''g'' = ''g''<sub>1</sub> ... ''g<sub>k</sub>'' be the desired factorization, where the ''g<sub>i</sub>'' are distinct monic irreducible polynomials of degree ''d''. Let ''n'' = deg(''g'') = ''kd''. We consider the [[ring (mathematics)|ring]] ''R'' = '''F'''<sub>''q''</sub>[''x'']/''g'' and denote also by ''x'' the image of ''x'' in ''R''. The ring ''R'' is the direct product of the fields ''R<sub>i</sub>'' = '''F'''<sub>''q''</sub>[''x'']/''g<sub>i</sub>'', and we denote by ''p<sub>i</sub>'' the natural [[homomorphism]] from the ''R'' onto ''R<sub>i</sub>''. The [[Galois group]] of ''R<sub>i</sub>'' over '''F'''<sub>''q''</sub> is cyclic of order ''d'', generated by the [[field automorphism]] ''u'' → ''u<sup>p</sup>''. It follows that the roots of ''g<sub>i</sub>'' in ''R<sub>i</sub>'' are
:<math> p_i(x), p_i(x^q), p_i \left (x^{q^2} \right ), \cdots, p_i \left (x^{q^{d-1}} \right ).</math>
Like in the preceding algorithm, this algorithm uses the same [[subalgebra]] ''B'' of ''R'' as the [[Berlekamp's algorithm]], sometimes called the "Berlekamp subagebra" and defined as
| |||