Constructing add/multi tables for GF(2)

692 Views Asked by At

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
1

There are 1 best solutions below

8
On BEST ANSWER

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.