XOR Defines an Abelian Group
Something I realized in the middle of an introductory course on cryptography when the instructor said the word “commutative” for the first time: N-bit strings with the operation XOR are an abelian group.
To verify this consider, the five properties we need to verify:
- Closure
- Identity
- Commutativity
- Inverses
- Associativity
Closure is trivial: an N-bit string XOR’d with an N-bit string gives an N-bit string.
The identity element is the N-bit string of all zeroes because 0 ^ 0 = 0 and 1 ^ 0 = 0 ^ 1 = 1. Note here that in XOR each bit operation can be considered independent of all other bits. E.g. in A ^ B = C the values of the seventh bits in A and B have no effect on the second bit of C.
And because the bits are independent, 0 ^ 1 = 1 = 1 ^ 0 implies commutativity for all n-bit strings.
Similarly, each element is its own inverse because 0^0 = 0 and 1^1 = 0.
Associativity is the trickiest one to prove, but still not difficult, since there only eight cases to check, even without taking advantage of commutativity:
- (0^0)^0 = 0^(0^0)
- (0^0)^1 = 0^(0^1)
- (0^1)^0 = 0^(1^0)
- (1^0)^0 = 1^(0^0)
- (1^1)^0 = 1^(1^0)
- (1^0)^1 = 1^(0^1)
- (1^1)^0 = 1^(1^0)
- (1^1)^1 = 1^(1^1)
Do the other bitwise operations form groups? I.e. AND (&), OR (|) or NAND? Doubtful. Consider AND on a 1-bit string:
- 0 & 1 = 0
- 0 & 0 = 0
- 1 & 0 = 0
- 1 & 1 = 1
1 is the identity. However 0 does not have an inverse.
For OR, 0 is the identity but 1 does not have an inverse.
NAND doesn’t even have an identity.
The next obvious question is what other finite groups are these groups isomorphic too? After a little googling, it looks like these are called “Boolean groups“, and are a subclass of something called “elementary abelian groups” (in which each element has a fixed prime order p. In Boolean groups p = 2.) In this case, the groups are all of order 2n (2, 4, 8, etc.) And it’s pretty easy to show that not all values of n have Boolean groups. In particular for any finite prime order, the group is a cyclic group; and in cyclic groups of order greater than two, the inverses all have the form (am)-1 = an-m. I.e. no elements are their own inverses so there can’t be any Boolean groups of prime order greater than 2. I don’t immediately know whether all Boolean groups have order 2n, or whether any such group of order n is isomorphic to the set of n-bit strings under XOR, but I haven’t given it a great deal of thought just yet. This Wikipedia article suggests that the answer to the second question at least is yes, but I’m not sure of there’s a straightforward way to prove this.
What else can we say about these groups? First we can extend them to an infinite abelian group over the non-negative integers. I.e. the XOR operation defined on the customary binary representation of an integer, and zero-extended as necessary in the most significant bits, satisfies all the group algorithms. That’s a bit of a surprise. I didn’t expect to find an infinite abelian group in the integers other than the usual ones based on addition. A little googling shows there’s a name for this. A group in which every element has finite order is called a “torsion group”. There are some other groups out there, but surprisingly they don’t seem to show up in introductory textbooks even though they’re easy to understand, and show just how general this really is.
Another thing we can say about these groups is that they are not simple (except for the trivial case of order 2). I.e. they contain non-normal subgroups. To construct a subgroup, take the subset of the n-bit strings with one or more bits fixed at zero) and since these groups are abelian, these subgroups are normal.
Furthermore, it’s straight-forward to prove that all Boolean groups (not just XOR groups, if there is a difference) are abelian. To show this follow these steps where a and b are any two elements of a Boolean group:
- (ba)(ba) = e
- babaa = ea = a
- bab = a
- bbab = ba
- ab = ba
XOR can be thought of as addition modulo 2, bit by bit without carries. Suppose we go beyond binary to digit wise modular addition? E.g. in base 10 23+45=68 and 86+97=73? Does that form a group? Yes, it does. The identity is zero. It’s obviously closed. And all other properties follow because the Z / 10 is a group under addition. In fact, this seems to be a general procedure for building larger groups out of smaller ones. Just concatenate n elements of the group together and define a new operation that’s the old operation operating piecewise on the components. Any such group would contain a subgroup in which one or more pieces was fixed to the identity element. Furthermore, the groups don’t have to be the same. For instance, you can define a group that’s O(2) × Z+ or any other two groups you care to name. I think this is called a “direct sum”.
I really wish the professor had mentioned this in the first lecture. It would have made a lot of the proofs and homework much more obvious, and saved me a lot of time writing out truth tables to verify his claims.
January 20th, 2013 at 9:06 am
I like this post. I writed an post in my blog about xor operation too.
http://marathoncode.blogspot.com.br/2012/02/tutorial-sobre-xor.html
January 21st, 2013 at 6:52 pm
For your next trick, try this in C or C++ with a pair of integers a and b — the result is kind of obvious, but it’s neat anyway:
a^=b^=a^=b;
I think you’ll like it. Note that the same operation also works on large memory-mapped structures such as arrays (or screens). Interestingly, in C# you have to write it as a^=b;b^=a;a^=b; or it renders one of the variables to zero. Something to do with compiler optimization, I think. Anyway, it’s a useful trick… a little bit write-only, but useful nonetheless.
January 30th, 2013 at 12:40 pm
@Dan – it’s nothing to do with complier optimization; it’s operator associativity.
test
In C++ the code is equivalent to ((a ^= b) ^= c) ^= d (which is not valid C#)
In C# the code is equivalent to a ^= (b ^= (c ^= d))
January 30th, 2013 at 12:59 pm
I take that back, what I said was nonsensical.
You’ve got me intrigued why the C# version doesn’t work.
July 17th, 2015 at 9:30 am
I read this post fully concerning the resemblance of most up-to-date and preceding technologies, it’s amazing article.
February 23rd, 2017 at 6:44 pm
I don’t think that {0,1}^N strings with XOR define a group at all. By definition a group needs to have one and only one identity element. This is not the case as you have already pointed out.
November 9th, 2017 at 8:27 am
@Jim, do you imply there’s another identity? If yes, then, what is the other identity?
July 24th, 2018 at 4:51 pm
It’s not possible for a binary operation to have multiple unique identities.
Assume the operator a $ b has 2 identities E1 and E2.
Then for all a, a $ E2 = a,
and for all b, E1 $ b = b.
So, E1 $ E2 = E1,
and E1 $ E2 = E2.
making E1 = E2.
So, there is still only one unique identity.