3
$\begingroup$

I've been reading the Reason why “XOR” is a linear operation, but ordinary “addition” isn’t? question, in which one of the answers states that addition modulo $n$ ($n>2$) is linear in $\mathbb{Z}_n$ but not in $\mathbb{F}_2$, it also states that - conversely - $XOR$ is linear in $\mathbb{F}_2$ but not in $\mathbb{Z}_n$($n>2$).

But in what sense?

I mean, how can I think about a $n$ ($n>2$) modular addition in $\mathbb{F}_2$?

When I've to sum modulo $n$ I usually sum the digits modulo $10$ (or directly reducing them modulo $n$ before doing the sum) and then reduce the result modulo $n$

F.i.: Taking $n = 3, x_1=2, x_2=2$

$$x_1+x_2 = 2+2 = 4 = 1 \pmod 3$$

But how can I think about a sum modulo $n$ in $\mathbb{F}_2$ ? And why it isn't linear in $\mathbb{F}_2$?

Conversely, how can I think about a $XOR$ in $\mathbb{Z}_n$, and why it isn't linear?

$\endgroup$
  • 1
    $\begingroup$ In order for it to make sense, you must set a field $K$, two $K$-vector spaces $V$ and $W$, and a map $f: V \to W$. Then you can talk about whether $f$ is linear. $\endgroup$ – fkraiem Jul 13 '16 at 2:03
  • $\begingroup$ @fkraiem If "linearity" stands for linear function/linear map, yes. In that answer, it seems more like "linear equation", or along the lines of a linear polynomial function (in the calculus meannig, with degree 1) $\endgroup$ – tylo Jul 13 '16 at 11:23
4
$\begingroup$

Sicne your question is refering to an answer on this site, I will not quote the entire answer here. But the crucial point is there in the last paragraph:

If none of that made any sense to you, that's OK. You just need to read up about Abstract Algebra, and Fields, Rings and Groups. It's a fascinating and beautiful area of mathematics, and much of cryptography will make no sense without at least some understanding of it.

I can only suggest you do the same and carefully read the answer again, because $\mathbb{F}_2$ was not mentioned in the answer at all. It contained statements about (finite) fields of Characteristic 2, which are $\mathbb{F}_{2^k}$ for any integer $k$.

If you carefully read the statements again, you will see that $\mathbb{F}_2$ actually meets both criteria, being a finite field of characteristic 2 and being a ring of the form $\mathbb{Z}_n$. In fact, XOR and modular addition are the very same group operation. It is quite obvious in this example, but could easily be checked by writing down the operator tables.

Considering your real question about linearity in finite fields, let's look at $\mathbb{F}_4$, which has characteristic 2, and is also described in the according Wiki article. So we got $\mathbb{F}_4 = {0,1,a,1+a}$, where addition is just the normal addition of polynomials, coefficients are reduced modulo 2, and multiplicaion is the regular multiplication of polynomials modulo $X^2+X+1$.

Unfortunately, the answer in question has a few points, which only make sense under a certain point of view. Basically, if you consider a number in a binary format, and then interpret each bit as a coefficient in $\mathbb{F}_{2^k}$ (see above construction for $\mathbb{F}_4$, with 2 coefficients before $a$ and a constant $1$), then XOR-ing numbers can be interpreted as the actual addition of polynomials in that finite field. However, you can't express XOR in $\mathbb{Z}_4$ as a linear equation - which has a quite different meaning than linear function in algebra. Analog, you can't express addition modulo 4 (in $\mathbb{Z}_4$) as linear equation in the field $\mathbb{F}_4$.

As a final note I can only say: Notation and details matter a lot in algebra. Especially if you don't understand the exact statement, this becomes even more important to avoid confusion - or even worse, that you learn something that is just false.

$\endgroup$
  • $\begingroup$ It is unclear to me what is meant by representing a function (such as XOR) as a linear equation. I think what is missing in this answer, is that the linearity of a map is inherently connected to the algebraic structure of its related objects, i.e. the modules under consideration. $\endgroup$ – Aleph Jul 15 '16 at 22:19
  • $\begingroup$ @Aleph I don't really understand what you mean. The expression "linear" is quite overloaded in this context, because "linear map" and "linear equation" are different concepts of linearity, but maybe I didn't point that out clear enough. And to come back to the original answer refered to: the expression "(linear) map" was not used there either. As I wrote: Details and notation matter. $\endgroup$ – tylo Jul 18 '16 at 10:24
  • $\begingroup$ And as J.D. gave a more elaborate explanation of his answer (the one refered to in the question), it is quite clear, that the property of linear maps has nothing to do with it, but it was all about expressing group operations as linear equations. $\endgroup$ – tylo Jul 18 '16 at 10:27
  • $\begingroup$ I don't really think that linear equations and linear maps are different concepts of linearity. A linear map is a homomorphism of modules. A (homogeneous) linear equation asks for the kernel of such a homomorphism. Anyway, I was referring to the specific sentence "you can't express XOR in $\mathbb Z_4$ as a linear equation". $\endgroup$ – Aleph Jul 19 '16 at 20:55
  • $\begingroup$ @Aleph To avoid repetition, J.D. already noted down how to express $a \oplus b$ with the normal ring operations in $\mathbb{Z_4}$, which is clearly not a linear equation (and not homogeneous). I tried to explain the answer refered to in the question, I did not come up with the whole point of different representations between natural numbers and their binary expansion with the XOR relation. $\endgroup$ – tylo Jul 20 '16 at 12:03
2
$\begingroup$

Well, as the author of the answer you cited, I can't much improve on tylo's answer. However, perhaps a couple of examples will be an useful supplement.

First, note that for $a,b \in \mathbb{Z}_4$: $$a \oplus b \equiv a + b + 2ab \pmod 4$$ Where the $\oplus$ on the left side means XOR and on the right side are addition and multiplication modulo 4. In other words, you can express XOR in $\mathbb{F}_4$ using an equation with addition and multiplication modulo 4, but notice that the equation (well, congruence) is not linear on the right hand side because it involves a term that multiplies two variables. That is what I meant by XOR not being expressible as a linear equation in $\mathbb{Z}_n$ for $n>2$.

Similarly, you can express addition modulo $2^n$ in terms of $n$ equations with bits as variables where XOR is addition and bitwise AND is multiplication (i.e. as equations in $\mathbb{F}_2$). Let $a_0$ and $b_0$ be the least significant bits of two $n$-bit strings $A$ and $B$, (and $a_{n-1}$ and $b_{n-1}$ conversely be the most significant bits). The string $C$, where $C\equiv A+B \pmod {2^n}$, can be expressed by the following system of equations: $$c_0 = a_0 + b_0 \\ c_1 = a_1 + b_1 + y_1 \\ ... \\ c_{n-1} = a_{n-1} + b_{n-1} + y_{n-1}$$ These equations appear to be linear, but aside from the first one they all include temporary variables for the carry bits, denoted by $y_x$ which have a nonlinear expression involving multiplication of variables (i.e. bitwise AND): $$y_1 = a_0b_0 \\ y_2 = a_1b_1 + (a_1 + b_1)y_1 \\ ... \\ y_{n-1} = a_{n-2}b_{n-2} + (a_{n-2} + b_{n-2})y_{n-2}$$

$\endgroup$

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.