1
$\begingroup$

i need some help with a product in GF(16), where it is seen as an extension of GF(4)={0, 1, x, x+1} (where $x^2 = x + 1$ ) with the irreducible polynom $f(y) = y^2 + y + x$

So the elements in the fields are: $\{0, 1, x, x+1, y, y + 1, y + x, y + x + 1, xy, ... \}$

I'm try to multiply $((x+1)y + x) * (xy + x + 1)$ and i obtain as result $(x + 1)$

I'm not sure that it is the correct result, can you help me?

Thank you, greetings

  • 0
    Indeed that's wrong -- it even contains two mistakes. The coefficient of $y$ in the second expression should be $x^2+x^2+1$, not $x^2+x^2+x$, since $(x+1)(x+1)=x^2+1$; and the "constant" term (in $y$) should be $x^2+x$, not just $x$. If you correct both of those mistakes, the result is the one you obtained.2012-01-03

1 Answers 1

2

Use the identities $x^2 = x+1$, $y^2 = y+x$, and $2=0$. After that you just have to compute. Here it goes explicitly for you to be confident : \begin{align} ((x+1)y+x) \times (xy + x + 1) & = ((x+1)y+x)xy + ((x+1)y+x)x + (x+1)y+x \\ & = (x^2y^2+xy^2+x^2y)+(x^2y + xy + x^2) + xy + y + x \\ & = x^2 y^2 + xy^2 + x^2 + y + x \\ & = x^2 (y+x) + x(y+x) + x^2 + (y+x) \\ & = (x^2 + x + 1)(y+x) + x^2 \\ & = (2x^2)(y+x) + x^2 = x^2 = x+1. \end{align} If there is a way to make this shorter I haven't looked for it.

Hope that helps,

  • 2
    Shorter way using FOIL: \begin{align*} ((x+1)y+x) \times (xy + x + 1) &= (x^2+x)y^2 + (x^2+(x+1)^2)y+(x^2+x) \\ &= y^2+(x^2+ x^2+1)y + x^2+ x \\ &= y^2 + y + (x^2+x) \\ & = x^2 = x+1. \end{align*}2012-01-03