0
$\begingroup$

I know that $XOR$ is equivalent to modular addition in the field $\mathbb{F}_2 = \{0,1\}$ (is it right?), and thus should satisfy the following property of a bilinear form:

$$\oplus(u+v,w) = \oplus(u,w) + \oplus(v,w)$$

My doubt is: how has the $+$ in the previous formula to be interpreted? Because if I interprete it like the same $XOR$ (even if looking at the formula it seems not to make much sense), applying the property I think I would have:

$$(u\oplus v) \oplus w = (u \oplus w) \oplus (v \oplus w) = u \oplus v $$

Even though I was expecting a result like:

$$ u \oplus v \oplus w$$

If the interpretation of the $+$ like the $\oplus$ is not the right interpretation, how has it to be interpreted, even considering that the normal $+$ and the $\oplus$ coincide in $\mathbb{F}_2 = \{0,1\}$?

At the end, what's the meaning of that property?

$\endgroup$
1
$\begingroup$

Actually, as you note, XOR doesn't satisfy the bilinear condition.

What does is multiplication $\otimes$ in $\mathbb{F}_2$, that is:

$$\otimes(u \oplus v, w) = \otimes(u,w) \oplus \otimes(v,w)$$

or, as more traditionally expressed (using $+$ and $\times$ as the field operations):

$$(u+v) \times w = (u \times w) + (v \times w)$$

This is one of the fundamental properties of a field; since $GF(2)$ is a field (with $\oplus$ and $\otimes$ as the field addition and field multiplication), this holds.

And, in $GF(2)$, $\otimes$ is equivalent to bitwise $AND$

| improve this answer | |
$\endgroup$
  • $\begingroup$ so $\oplus$ is not bilinear? $\endgroup$ – Alessio Martorana Jul 12 '16 at 10:36
  • $\begingroup$ No, $\otimes$ is blinear (over $\oplus$) $\endgroup$ – poncho Jul 12 '16 at 12:06
  • $\begingroup$ But is $\oplus$ a linear operation? $\endgroup$ – Alessio Martorana Jul 13 '16 at 1:43
  • $\begingroup$ @AlessioMartorana: yes, it is (over the group $GF(2)$, which is a bit tautological when you think about it...) $\endgroup$ – poncho Jul 13 '16 at 3:24
  • $\begingroup$ I was asking precisely that: what is the difference between being linear in $GF(2)$ or in, for example, $\mathbb{Z}_n$ ? What's the meaning of this? And why $\oplus$ is linear in $\mathbb{F}_2$ and not in $\mathbb{Z}_n$, what does not happen? $\endgroup$ – Alessio Martorana Jul 13 '16 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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