3
$\begingroup$

What does $GF(2)[x]/(x^3-1)$ mean? I know $GF(2)$ is the Galois field with 2 elements, but what does the forward slash mean? Also, what's the meaning of the entire expression?

Thanks!

  • 0
    Numerator means the polynomials in indeterminate x with coefficients in GF(2). The /(x^3-1) means "mod x^3-1" i.e. two polynomials are considered the same if they give the same remainder on division by x^3-1.2011-04-20

1 Answers 1

3

$\mbox{GF}(2)$ is the finite field with 2 elements (one of the rare instances in mathematics where the common name for an object is kind of larger than the object itself).

$\mbox{GF}(2)[x]$ is the ring of polynomials in the variable $x$ with coefficients in that field. If you're not sure what this means, you should probably learn about this first before you tackle the expression at hand. Let's call this ring $R$.

$x^3-1$ is a specific polynomial in that ring. Since the field is $\mbox{GF}(2)$, it's actually the same polynomial as $x^3+1$.

$(x^3-1)$ is the ideal generated by that polynomial: it's all the polynomials of the form $(x^3-1)f(x)$ where $f(x)$ is an arbitrary polynomial over $\mbox{GF}(2)$. Let's call this ideal $I$.

The forward slash means "quotient" - the quotient of ring $R$ by the ideal $I$, denoted $R/I$. One good way to think about it is as the the set of polynomials of degree 2 (or less), endowed with the operations of ordinary polynomial addition and ordinary multiplication except that after multiplying you take the remainder of the result upon division by $x^3-1$.

  • 0
    thanks for the detailed answer! I'd appreciate it if you can clarify 3 more questions: 1. In $GF(2)[x]$, why is the x bracketed? Is it related to modulo? 2. why is $R/I$ the set of polynomials of degree 2 or less? I mean, why can't the degree be greater than 2? 3. You said $(x^3-1)$ is the ideal generated by "that" polynomial. Does "that" refer to any polynomial over $GF(2)$? thanks again!2011-04-20
  • 2
    1. For any ring $R$, the ring of polynomials in the variable $x$ with coefficients in $R$ is denoted $R[x]$. That's where the brackets come from and it has nothing to do with any modulo.2011-04-20
  • 2
    2. In $R/(f)$ where $f$ is a polynomial, we're allowed to replace any polynomial by its residue modulo $f$. That's what "quotienting $f$ out" means. Since in your case $f$ has degree 3, any polynomial can be replaced by an equivalent one of degree 2 or less. For example, in the quotient ring, $x^3$ is the same as $-1$, and $x^4$ is the same as $x$. We might as well choose representatives of degree 2 or less.2011-04-20
  • 2
    3. No, of course not! $(x^3-1)$ is the ideal generated by $x^3-1$.2011-04-20