Content deleted Content added
No edit summary |
→Background: \align |
||
Line 12:
<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 sum]] of factor rings <math>S = \bigoplus_{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>
:<math>g(x) \equiv g_1(x) \pmod{p_1(x)},</math>▼
\begin{align}
g(x) & {} \equiv g_2(x) \pmod{p_2(x)}, \\
\end{align}
▲:<math>g(x) \equiv g_s(x) \pmod{p_s(x)},</math>
</math>
then <math>\phi(g(x) + \langle f(x) \rangle) = (g_1(x) + \langle p_1(x) \rangle, \ldots, g_s(x) + \langle p_s(x) \rangle)</math>. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the <math>p_i(x)</math> are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree <math>q^d</math>.
| |||