Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was unable to solve the multiplication table given in the book for $\mathrm{GF}(2^2)$.However, I have managed to solve the addition table.

Acoording to the Book multiplication is the AND operation, but when I applied this I did not get the answer given in the book.

This is the Table given in the book:

enter image description here

I couldn't replicate the same answers for 10x10 or 11x11.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

$\mathrm{GF}(2^2)$ is the finite field of 4 elements, and has minimal polynomial $x^2+x+1$. Throughout this question I will use $ab$ to denote $ax+b$ (ie $10=1*x+0$) - this is standard notation when considering finite fields over $\mathbb F_2$ since it aligns with how we consider bits in bytes.

As you have already seen, addition is done by bitwise xor:
$ab+cd := ab\oplus cd$

For multiplication, we do standard polynomial multiplication, but then must reduce by the minimal polynomial. That is, we use the identity that $x^2=x+1$. So:

$$\begin{aligned} ab\cdot cd &= (a*x+b)(c*x+d) \\ &= (a * c)x^2+(a* d + b * c)x + b*d \\ &= (a* d + b * c + a * c) x + [b*d + a * c] \end{aligned}$$ Now, as discussed above + is xor (denoted $\oplus$), and the hint given by your book is that multiplication of the coefficients is the same as an AND operation (which I'll denote with $\&$):

$$\begin{aligned} ab\cdot cd &= (a\&d \oplus b\&c \oplus a\&c) x \oplus [b\&d \oplus a\&c] \\ &= [a\&d \oplus b\&c \oplus a\&c][b\&d \oplus a\&c] \end{aligned}$$

share|improve this answer

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.