0

I started learning about finite fields and came across this problem online and I haven't seen this format before:

R=GF(2)[x] mod x^3 + 1 = 0

What is the x part for? The closest I've seen is GF(3) = Z, *; mod 3. And the multiplication table looks like this:

*|0|1|2
0|0|0|0
1|0|1|2
2|0|2|1
azimut
  • 22,696
pfinferno
  • 307

1 Answers1

0

For any commutative ring $A$, $A[x]$ stands for set of polynomials with coefficients from $A$. Using addition and multiplication from $A$, one can turn $A[x]$ into a ring in a canonical manner. It is known as the polynomial ring over $A$ in one indeterminate $x$.

For any non-zero polynomial $p(x) \in A[x]$ the notation $A[x] \text{ mod } p(x)$, or more commonly $A[x]/p(x)$ stands for the quotient space of $A[x]$ under the equivalent relation $\sim$

$$f(x) \sim g(x) \quad\iff\quad p(x)|(f(x) - g(x)) \quad \text{ for any } f(x), g(x) \in A[x]$$

i.e. $f(x)$ and $g(x)$ corresponds to same element in $A[x]/p(x)$ when and only when they differ by a multiple of $p(x)$.

What you have been asked is to compute the addition/multiplication table when $A = GF(2)$ and $p(x) = x^3 + 1$. It has $8$ elements

$$0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1$$

For example,

$$\require{cancel} (x+1)(x^2 + x) = x^3 + \color{red}{\cancelto{0}{\color{gray}{2}}}x^2 + x = x^3 + x = \color{red}{\cancelto{0}{\color{gray}{(x^3 + 1)}}} + (x+1) = x+1 $$

The remaining $63$ products are similar. It is just tedious to compute them by hand. You should compute a few of them by hand and then write a little program to verify you compute them correctly. This have the additional benefit to strengthen your understanding.

achille hui
  • 122,701
  • Hmm, so the 2 in GF(2) stands for the highest coefficient I can use w/ the polynomials? – pfinferno Sep 13 '15 at 15:18
  • Your post sort of makes sense but I don't think I'm getting it. Where exactly do those 8 elements come from? Is that just from breaking down x^3 + 1? – pfinferno Sep 13 '15 at 15:29
  • When the $n$ inside $GF(n)$ is a prime. Yes. it is the highest coefficient you can use w/ the polynomials. More precisely, for prime $p$, $GF(p) = \mathbb{Z}/p\mathbb{Z}$ is the equivalent class of integers under arithmetic module $p$. There are other $n$ where $GF(n)$ is a field, all of them has the form $n = p^k$ and can be realized as $GF(p)[x]/f(x)$ for some irreducible polynomial $f(x)$ of degree $k$. Since all finite field with same size is isomorphic to each other, people just write $GF(p^k)$ for any finite field with $p^k$ elements. – achille hui Sep 13 '15 at 15:29
  • About the $8$ elements, if you divide any element in $GF(2)[x]$ by $x^3 + 1$ with long division, you will have $8$ possible remainders. The list above is that 8 possible remainders. – achille hui Sep 13 '15 at 15:32
  • Okay, I guess my last question is, what exactly are the elements in GF(2). How do I go about finding those so I can divide them by whatever polynomial is listed? – pfinferno Sep 13 '15 at 15:54
  • $0$ and $1$ or more precisely, the set of even and odd integers. You just work under modular arithmetic for modulus $2$. – achille hui Sep 13 '15 at 15:57
  • So wait, I'm dividing 0 and 1 by x^3+1 ? (Can move this discussion to chat if you're free) – pfinferno Sep 13 '15 at 16:15
  • Oh! I think I get it now! The coefficients can't be higher than 2 when making the polynomials. So when I get to x+1, I can't do x + x or 1 + 1, so I square the x, then x^2 + 2, etc, until I reach the 8 elements. Then I do one of those + or * whatever column/row I'm at, and mod that by the given polynomial. In this case it would be x^3 + 1. – pfinferno Sep 13 '15 at 20:09