The Artima Developer Community
Sponsored Link

Java Buzz Forum
XOR Defines an Abelian Group

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
Elliotte Rusty Harold

Posts: 1573
Nickname: elharo
Registered: Apr, 2003

Elliotte Rusty Harold is an author, developer, and general kibitzer.
XOR Defines an Abelian Group Posted: Nov 26, 2012 4:34 AM
Reply to this message Reply

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

Advertisement

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.


Read: XOR Defines an Abelian Group

Topic: Polling an http end point using Spring Integration Previous Topic   Next Topic Topic: Functional Testing of Dynamic Websites with Grails and Geb

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use