# Exploring Groups and Codes with Python

#### Part 2: Introducing Groups

by
Kirby Urner
First Posted: March 21, 2001
Last Updated: July 15, 2001

 For a set of elements to comprise a group vis-a-vis some definition of a binary operator, such as * (multiplication) or + (addition), they need to combine associatively, but not necessarily commutatively. In other words, how you group your multiplications doesn't matter, so long as order is preserved. But when multiplication is not commutative, changing the order of the multiplications will likely change the outcome. If the operation for which the group is defined turns out to be commutative, as well as associative, the group is said to be Abelian. The complete set of properties you need to be a group are: Closure: the product of two elements in the set is always itself in the set Associativity: p1 * p2 * p3 has an unambiguous meaning i.e. (p1 * p2) * p3 and p1 * (p2 * p3) give the same result Inverse: every element has an inverse such that the product of the two is the identity element Neutral element: some element e, called the identity element, has a "neutral effect" when multiplying other elements i.e. p * e = e * p = p. These four properties spell CAIN, an easy mnemonic, especially in light of Abelian groups, named for the mathematician Niels Henrik Abel (1802 - 1829) -- but also the name of Cain's brother in the well-known Genesis story. You'll see below that our domain of alphabet or integer permutations under multiplication is a non-Abelian group, i.e. * is a non-commutative, but associative operation. But first, we need some permutation objects to play with. Let's start with some simple integer-based ones. >>> from ciphers import * # asterisk means "all" here >>> p1=P() >>> p2=P() >>> p1 Permutation: [(8, 5, 2, 6, 7, 4, 1)] >>> p2 Permutation: [(10, 7, 6, 8, 2, 5, 1), (9, 4, 3)] When objects of class P are initialized with no arguments, we simply shuffle the a default domain, internal to the object, and create a substition dictionary of unshuffled:shuffled key:value pairs. This default domain is the integers 1 through 10. If the goal is to define a specific permutation, then either the substitution dictionary, or the equivalent list of cycles may be passed as a parameter. class P: """ Permutations: these objects multiply with each other, return an inverse, may be raised to an integer power """ domain = range(1,11) def __init__(self, cycles=None, dict =None, domain=None): """ Accept permutation in cyclic notation, or as a substitution dictionary. A random permutation is returned if neither is provided, using domain as the list of elements to permute (default = 1-10) """ if domain != None: self.domain = domain if cycles==None and dict==None: # shuffle default internal domain self.dict = self.randpermute() elif cycles != None: self.dict = self.mkdict(cycles) else: self.dict = dict self.domain = dict.keys() Multiplication is defined as follows: classP: ... def__mul__(self,other): newdict = {} for i in self.dict.keys(): newdict[i] = other.dict[self.dict[i]] return P(newdict) Now we're ready to demonstrate non-commutativity: >>> p1*p2 Permutation: [(10, 7, 3, 9, 4), (8, 1, 2)] >>> p2*p1 Permutation: [(10, 4, 3, 9, 1), (8, 6, 5)] Remember, these cyclic expressions are another way of presenting the same info as held by a substitution dictionary. In the previous post, the dict2cycles(dict) method was introduced, for going from a dictionary to a list of tuples. This method is built in to the P class, as it's method for self-representation: classP: ... def__repr__(self): return "Permutation: " + str(self.mkcycles()) p1 * p2 applies p2 to p1, so after we take 7 to 4, we take 4 to 3, so in the product, 7 maps to 3. Demonstrating associativity: >>> p3 Permutation: [(9, 6, 7), (8, 5), (4, 2, 1, 3)] >>> p1*(p2*p3) Permutation: [(10, 9, 2, 5, 8, 3, 6, 7, 4)] >>> (p1*p2)*p3 Permutation: [(10, 9, 2, 5, 8, 3, 6, 7, 4)] Or we could have done: >>> p1*p2==p2*p1 0 >>> p1*(p2*p3)==(p1*p2)*p3 1 The method for determining equality simply compares the internal dictionary of two objects: classP: ... def__eq__(self,other): return self.dict==other.dict Note: some specific p1, p2 may commute, e.g. if p1 and p2 are inverses -- it's just that they need not. The operation * is not in general a commutative operation in this realm of permutations. Using a P-class dictionary, we can encipher a message. Let's make p1 the result of 4 random permutations, intermultiplied (itself a permutation -- by virtue of Closure): >>> P.domain = list(string.uppercase) >>> p1 = P() * P() * P() * P() >>> p1 Permutation: [('Z', 'K', 'C', 'N', 'U', 'M', 'B', 'Y', 'H', 'R', 'I', 'P', 'E', 'L', 'W', 'O', 'D', 'Q', 'T', 'J', 'X', 'G', 'F', 'S'), ('V', 'A')] Let's make p2 be the inverse of p1 (every p has an inverse), i.e. its internal dictionary is a reverse version of p1's: >>> p2 = ~p1 >>> p2 Permutation: [('Z', 'S', 'F', 'G', 'X', 'J', 'T', 'Q', 'D', 'O', 'W', 'L', 'E', 'P', 'I', 'R', 'H', 'Y', 'B', 'M', 'U', 'N', 'C', 'K'), ('V', 'A')] We see that to decrypt is to reverse the process of encryption, which in this case means encrypting the ciphertext using the inverse permutation (p2): >>> p1.encrypt("ABLE WAS I ERE I SAW ELBA") 'VYWL OVZ P LIL P ZVO LWYV' >>> p2.encrypt("VYWL OVZ P LIL P ZVO LWYV") 'ABLE WAS I ERE I SAW ELBA' Because multiplication is not commutative, i.e. is "order-sensitive" with respect to permutations, we should pause to explore an effective strategy for using inverses to undo a series of permutations. Somewhat like Theseus in the maze with the Minotaur, we need to follow a thread of inverse permutations that precisely reverses the pathway just traversed. We must retrace our steps, undoing the most recent permutation first, and then the next most recent and so on. The Rubik's Cube also provides a good example of a non-commutative environment. If you twist the top layer and then one of the sides, clockwise both times, and then twist the top and side again, in that order, counter-clockwise, you will not be back where you started. To retrace your steps you would have needed to reverse the side-twist (most recent op) and then the top twist. Consider the following interactions at the command line interface: >>> P.domain = list(string.uppercase) >>> p1,p2,p3,p4 = P(),P(),P(),P() # 4 permutations >>> invp1, invp2, invp3, invp4 =[~p for p in [p1,p2,p3,p4]] >>> invp1*p1 # undoing an operation gets us "no change" (neutral element) Permutation: [] >>> invp2*p2*invp3*p3 Permutation: [] >>> invp1*invp2*invp3*invp4*p1*p2*p3*p4 # Undoing fails! Wrong order Permutation: [('Z', 'G', 'V', 'T', 'Q', 'X', 'K', 'S'), ('Y', 'P', 'R', 'D', 'E', 'L', 'W', 'I', 'O', 'U', 'H', 'M', 'A', 'F', 'N', 'B')] >>> invp1*invp2*invp3*invp4*p4*p3*p2*p1 # retracing our steps correctly Permutation: [] When we multiply a permutation by itself, that's like raising a number to a power, e.g. p1 * p1 may be written as p1 ** 2 -- ** is Python's exponentiation syntax -- or, alternatively, as pow(p1, 2). Likewise, ~p1 may be expressed as p1 ** (-1) or pow(p1, -1), since p1 * ~p1 = [] or the identity permutation. Raising p1 to the -3 power is equivalent to raising it to the 3rd power and then taking the inverse of the result, i.e. pow(p1, -3) = ~(p1 * p1 * p1): >>> pow(p1,-3) Permutation: [('Z', 'G', 'T', 'O', 'E', 'R', 'B', 'N'), ('X', 'Q', 'W', 'P', 'H', 'M', 'C', 'S'), ('Y', 'U', 'K', 'F', 'J', 'D', 'L', 'I'), ('V', 'A')] >>> ~(p1*p1*p1) Permutation: [('Z', 'G', 'T', 'O', 'E', 'R', 'B', 'N'), ('X', 'Q', 'W', 'P', 'H', 'M', 'C', 'S'), ('Y', 'U', 'K', 'F', 'J', 'D', 'L', 'I'), ('V', 'A')] The internal P-class __pow__ method simply invokes the already-define __mul__ repeatedly, inverting as necessary (i.e. if the exponent is a negative number). Also p1 ** 0 is defined to be the identity element, whereas p1 ** 1 is just p1 itself -- definition analogous to the behavior of * when used for the "regular" multiplication of integers or reals. classP: ... def__pow__(self,n): new = P([]) if n==0: return new for i in range(abs(n)): new = self * new if n<0: new = ~new return new By setting __xor__ = __pow__ in the class definition, we also allow p^3 as an alternative to p**3, i.e. the caret or ^ symbol becomes an alternative exponentiation operator (normally it's used for exclusive-or, but P-objects don't need it for that). When a permutation permutes itself, as in p1 * p1, the tuple elements skip ahead one notch, to pair with elements that had been 2 ahead: >>> p1 Permutation: [('Z', 'K', 'C', 'N', 'U', 'M', 'B', 'Y', 'H', 'R', 'I', 'P', 'E', 'L', 'W', 'O', 'D', 'Q', 'T', 'J', 'X', 'G', 'F', 'S'), ('V', 'A')] >>> p1^2 Permutation: [('Z', 'C', 'U', 'B', 'H', 'I', 'E', 'W', 'D', 'T', 'X', 'F'), ('Y', 'R', 'P', 'L', 'O', 'Q', 'J', 'G', 'S', 'K', 'N', 'M')] Whereas in p1, Z maps to K, in p1 ^ 2, Z maps to C, which was 2 ahead of K in p1. What this suggests is that any given tuple will eventually point all the way around the cycle back to the start, such that Z maps to Z, K to K and so on. But because the different tuples may have different lengths, they may not all reach this "identity position" at the same power. But is their some power where all the tuples are guarenteed to become the identity mapping, all at the same time? Yes! That would be the lowest common multiple of the lengths of all the tuples. With p1 above, the tuples have lengths 24, and 2. The lcm is 24, so p1 ^ 24 should be the identity element... >>> p1^24 Permutation: [] Let's try another one: >>> P.domain = list(string.upper) # newp = permutation of A-Z >>> newp Permutation: [('Z', 'E', 'G', 'N', 'W', 'Y', 'J', 'Q', 'X', 'F', 'M', 'L', 'T', 'A', 'K', 'H'), ('V', 'B', 'D', 'P', 'R', 'C', 'O', 'U', 'S')] >>> map(len,newp.mkcycles()) [16, 9] >>> lcm(16,9) 144 >>> pow(newp,144) Permutation: [] The power to which you need to raise permutation p to get the identity element is what we call the 'order of p'. We can build this into the P class as another method, ord( ): classP: ... deford(self): """ returns the exponent n of p such that p**n = [] (identity element) """ return reduce(lcm, map(len, self.mkcycles())) Usage: >>> newp.ord() 144 Given this definition, pow(p1, p1.ord( )) should always return the identity permutation, which we may initialize with the identity dictionary: >>> ident = P([]) # initialize P using identity dictionary >>> anyp = P() >>> pow(anyp,anyp.ord())==ident 1 Once anyp reaches the identity state, the next multiplication will get us back to the original anyp, and the cycle begins again, i.e. pow(anyp,1), pow(anyp,2)... pow(anyp,anyp.ord()) is a complete cycle of unique permutations based on a base of anyp. Our strategy for building a more sophisticated enciphering engine will be to have a set of permutations, which we will call "rotors", organized "odometer fashion" such that when the first powers itself around a complete cycle, it'll kick the second to the next power, and the second, when "once around the clock" will kick the third and so on. This is like having a mixed-base number (presuming the rotors have different orders, different periods), and counting up from 0 in that system. If the order of the first rotor is 7, then we would go 001, 002 ... 006, 010 -- p1 becomes the identity permutation just as p2 kicks up to its first power. The engine will run the counter up one click for each letter that gets enciphered, so the substitution dictionary will be constantly changing. This will remove the property of always having the same letter stand for some other letter. And, to make things even more difficult, we'll throw in the space character as one more "letter" to be enciphered, thereby obscuring word boundaries. Because this enciphering strategy is somewhat akin to that used during WWII by a number of encyption machines, including the famous Enigma, I'll call this my Enigma class. >>> P.domain = list(string.uppercase) + [' '] # A-Z and space >>> enigma = Enigma([P(),P(),P()]) # use 3 random rotors >>> enigma.counter.bases # the orders of these rotors [36, 132, 24] >>> enigma.encrypt("Able was I ere I saw Elba") 'BFC QVOBAXPKPBWQGECPVT EE' >>> enigma.reset() # return counter to [0,0,0], self.dict to [] >>> enigma.decrypt('BFC QVOBAXPKPBWQGECPVT EE') 'ABLE WAS I ERE I SAW ELBA' Notice the ciphertext is no longer palindromic -- isn't the same forwards and backwards, unlike the original. Plus word spacing has been effectively masked. Suddenly, our code is much harder to crack. The decryption method simply runs the rotors in reverse, and associatively "undoes" whatever was done by the encryption method, returning our ciphertext back to the plaintext original. Before we finish designing this machine, let's get some more background in Part 3. For further reading: Parts 1, 3 and 4 of Exploring Codes and Groups with Python Source code (py and html versions) Lecture notes on the mathematics of the Rubik's Cube by W. D. Joyner, U.S. Naval Academy Return to CP4E Oregon Curriculum Network