I am having difficulty understanding quotient rings with regards to polynomials. For example, the quotient ring $\mathbb{F_2}[x]/(x^3 + 1)$ maps to the set of all remainders when a polynomial of $x$ (with coefficients in $\mathbb{F}_2$) is divisible by $x^3 + 1$. However, it's hard for me to comprehend the exact elements in this quotient ring.
Obviously if the quotient ring is something like $\mathbb{Z}/5$, I know that it maps to the set $\{0, 1, 2, 3, 4\}$, since that is the set of possible remainders when any number is divided by $5$. However, with polynomials, I feel it's more difficult to understand because for instance, I know that when a polynomial of $x$ is divided by $x^3 + 1$, the remainder obviously has to be less than $x^3 + 1$, but a polynomial such as $x^2 + 1$ is greater than $x^3 + 1$ for the domain $(0, 1)$ but not so when $x > 1$. So I'm wondering if there's an objective algorithm to determine the set of all remainders when a polynomial is divided by another polynomial.
Best Answer
The notion of "size" we use when we quotient polynomial rings is not the absolute value, but the degree. So for instance, something like $100x^2 + 500$ (which is degree $2$) would be considered smaller than $x^5 - 50 x^4$ (which is degree $5$), because we only care about the degree.
As for how we compute residue classes, we use the same division algorithm that we're used to in order to compute a remainder. You can see a series of worked out examples here, say.
Now, if we look at $\mathbb{F}_5 = \mathbb{Z} / 5$, the elements we're left with are those which are "smaller" than $5$. So $\{0,1,2,3,4\}$.
If we look at $\mathbb{F}_3[x] / (x^3 - x^2 + 1)$, then the elements we're left with are those which are "smaller" than $x^3 - x^2 + 1$. That is, those polynomials of degree $< 3$. So the elements are
$$ \begin{align} 0 && 1 && 2 \\ x && x+1 && x+2 \\ 2x && 2x+1 && 2x+2 \\ x^2 && x^2 + 1 && x^2 + 2 \\ x^2 + x && x^2 + x+1 && x^2 + x+2 \\ x^2 + 2x && x^2 + 2x+1 && x^2 + 2x+2 \\ 2x^2 && 2x^2 + 1 && 2x^2 + 2 \\ 2x^2 + x && 2x^2 + x+1 && 2x^2 + x+2 \\ 2x^2 + 2x && 2x^2 + 2x+1 && 2x^2 + 2x+2 \\ \end{align} $$
Notice there are $27$ of these, since a general polynomial looks like $a_2 x^2 + a_1 x + a_0$, where each $a_i \in \mathbb{F}_3$.
In general, if $f$ is a polynomial of degree $n$, then $\mathbb{F}_p [x] / (f)$ will have $p^n$ elements for exactly this reason.
As a quick example of how to do reduction, let's reduce $x^4$ mod $x^3 - x^2 + 1$ in $\mathbb{F}_3[x]$.
The key insight is that since $x^3 - x^2 + 1 = 0$ in the quotient ring, we can rearrange this to see $x^3 = x^2 - 1$.
Now $x^4 = (x) (x^3)$, which, by the above argument is $(x) (x^2 - 1)$, or $x^3 - x$. Now we go again, since we still see an $x^3$, and this becomes $(x^2 - 1) - x$.
So then $x^4 = x^2 - x - 1$, and since we are working in a polynomial ring over $\mathbb{F}_3$, we can rewrite this as $x^2 + 2x + 2$, which would be the final answer.
Obviously it's tedious to have to repeatedly subtract off factors of $x^3$ and replace them, but thankfully we don't need to! In addition to the video I linked earlier, you can see a worked example for the division algorithm here which lets you efficiently compute $p(x)$ mod $f(x)$.
I hope this helps ^_^