Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 16:59, 18 November 2008

Revision as of 21:05, 22 March 2009

Line 10:

All possible factors of <math>f(x)</math> are contained within the [[factor ring]]

<math>R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}</math>. If we suppose that <math>f(x)</math> has irreducible factors <math>p_1(x), p_2(x), \ldots, p_s(x)</math>, all of degree <math>d</math>, then this factor ring is isomorphic to the [[direct sumproduct]] of factor rings <math>S = \bigoplus_prod_{i=1}^s \frac{\mathbb{F}_q[x]}{\langle p_i(x) \rangle}</math>. The isomorphism from <math>R</math> to <math>S</math>, say <math>\phi</math>, maps a polynomial <math>g(x) \in R</math> to the <math>s</math>-tuple of its reductions modulo each of the <math>p_i(x)</math>, i.e. if:

:<math>