Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Looks right to me. Maybe you should write it as $0y+(x+1)$ to emphasize that the result is an element of GF$(16)$ represented as a polynomial of degree at most $1$ in $y$, whose coefficients are elements of GF$(4)$, i.e. polynomials in $x$ of degree at most one in $x$. –  Dilip Sarwate Jan 3 '12 at 13:41
    
Ok, thank you Dilip. I'm studing on a book where i there is written that: $((x+1)y + x)*(xy + x + 1) = (x^2 +x)y^2 + (x^2 +x^2 +x)y + x =$ $ y^2 + xy + x = y+x + xy + x = y(x+1)$, but it looks wrong to me... (nb: it's using the same polynome to define the fields) –  Aslan986 Jan 3 '12 at 13:52
    
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. –  joriki Jan 3 '12 at 14:05

1 Answer 1

up vote 2 down vote accepted

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,

share|improve this answer
1  
Perfect, thanks. –  Aslan986 Jan 3 '12 at 14:17
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*}$$ –  Dilip Sarwate Jan 3 '12 at 17:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.