This post originated from an RSS feed registered with Java Buzz by Elliotte Rusty Harold. Original Post: XOR Defines an Abelian Group Feed Title: The Cafes Feed URL: http://cafe.elharo.com/feed/atom/? Feed Description: Longer than a blog; shorter than a book Latest Java Buzz Posts Latest Java Buzz Posts by Elliotte Rusty Harold Latest Posts From The Cafes

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:

1. Closure
2. Identity
3. Commutativity
4. Inverses
5. 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 N-bit finite groups are these groups isomorphic too? For prime order we know they’re isomorphic to the cyclic groups (because every group of prime order is cyclic) but for other orders? 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.)

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.