1
$\begingroup$

Let $f(x) = x^6 + x + 1$ and define the field $F = \mathbb{Z}_2[x]/f(x)$

Compute the following in this field:

1. $(x^5 + x + 1)(x^3 + x^2 +1)$

I start by multiplying (in $\mathbb{Z}_2[x]$):

$(x^5 + x + 1)(x^3 + x^2 +1)$ = $(x^8 + x^7 + x^5 +x^4 + x^2 + x + 1)$

Then dividing the result with $f(x)$:

$(x^2 + x)$ and the remainder $(x^5 + x^4 + x^3 + x^2 + 1)$

Is this the right approach for solving this problem? Do I understand it correct that I want the result of my multiplication mod $f(x)$? Can I think of it as a simple modulus calculation:

$11$ mod $7 = a$

$7*1 + 4$ mod $7 = 4$

In my case I have

$(x^6 + x +1)*(x^2 + x) + \mbox{remainder}$ mod $(x^6 +x + 1) = \mbox{remainder}$

So my answer to the question would be the remainder, $(x^5 + x^4 + x^3 + x^2 + 1)$?

2. $(x + 1)^{-1}$

I read (wiki) that the inverse to $(x + 1)$ could be found by using the extended euclidean alg. for $a = (x^6 + x +1)$, $b = (x+1)$ but I don't really get it since $a$ is irreducible.

Any hints in the right direction would be appreciated!

3 Answers 3

2

Your idea for (1) is correct.

As for (2), it is the same idea as for the ring of integers modulo $n$. The $gcd$ of $x+1$ and $x^6+x+1$ will be $1$ since $x+1$ and $x^6+x+1$ are coprime. Using the extended Euclidean algorithm you'll get $ A(x+1) + B(x^6+x+1) = 1 $ where $A, B \in \Bbb{F}_2[x]/f(x)$. So as you can see, modulo $x^6+x+1$ we have that $ A(x+1) \equiv 1 \pmod{x^6+x+1} $ and hence $A$ is the inverse of $x+1$.

NOTE: remember that in $\Bbb{Z}_2$ (which I hope you don't mean the $p$-adic integers), $-1 \equiv 1 \pmod{2}$.

  • 0
    About your note, you're right my answer in (1) should be $(x^5+x^4+x^3+x^2+1)$ since it's mod 2.2012-06-10
2

Your first idea is right, and I think you need to read the extended Euclidean algorithm over again (because $x^6+x+1$ being irreducible should not deter you.)

Dividing $\frac{x^6+x+1}{x+1}$ you'll find $(x+1)(x^5+x^4+x^3+x^2+x)+1=x^6+x+1$, and so $(x+1)(x^5+x^4+x^3+x^2+x)=1$ in the quotient.

  • 0
    Yeah I think I'm tired don't know what I was thinking.. That was what I got, just didn't see it. Thanks for the help!2012-06-10
2

$\rm In\ \,{\it any}\,\ ring\ with\ \ \color{brown}{x^{2n}\! -\! x\! +\! 1} \,=\, 0\ $ one easily inverts $\rm\:1\!-\!x\:$ as follows

$\rm\quad\ \ \ \, \dfrac{1 }{1\!-\!x}\, =\, \dfrac{1\!\color{brown}{-\!x^{2n}\!+\!x\!-\!1}}{1-x}\, =\, \dfrac{1\!-\!x^{2n}}{1\!-\!x\ \ \ } - 1\, =\, x\! +\! x^2\! +\! x^3\! +\cdots + x^{2n-1}$

Generally $\rm\:g\:$ has such an "easy" inverse mod $\rm\:f\:$ when $\rm\:g\:|\:f\!-\!1\:$ since then $\rm\:f = 1 + h\,g,\:$ hence $\rm\: mod\ f\!:\,-h\,g \equiv 1,\:$ i.e. $\rm\:g^{-1} \equiv -h.\:$ The same is true if $\rm\:g\:|\:f\! -\! u\:$ for a unit $\rm\:u.\:$ When this is true, the extended Euclidean algorithm terminates in one step. This happens so frequently for "small" problems that it is well-worth testing before initiating the general algorithm.