by ELorenz on Sun Apr 27, 2008 5:27 pm
([msg=1542]see Re: Interest in Math topics[/msg])
Here is the article that I wrote about Algebraic Groups.
Algebraic Groups
This is an introduction article to the theory of algebraic groups.
There are a few things you need to know before I get started. They are as follows:
Modulo arithmetic – modulo arithmetic, I will designate it by using mod n, is when you take the
remainder after division as the value. Basically the % operator in Java and
several other programming languages. For example 3 mod 2 = 1, if the
number is smaller than n then you just use the number. The code for this
process looks like 3 % 2 in Java code.
Sets – a set is a collection of elements. The elements can be just about anything, but in this article
I am going to limit the elements to the integers for ease of discussion.
Integers – the integers are the whole numbers from negative infinity to infinity, such as 1, 2, 3, etc.
The formal definition of a group given by the Encyclopedia Britannica is “a system consisting of a set of elements and an operation for combining the elements, which together satisfy certain axioms.” Basically you have a set and an operation, and the result of combining the two has to act a certain way. In this case I’m going to define the set, name it G, as the set if integers mod 5, which includes {0, 1, 2, 3, 4} and define the operation to be addition. The important thing to note is that the set can be just about anything as long as when it is combined with the operation you choose it acts the way it is supposed to. For example you can have sets of functions, permutations, matrices, symmetries, deformations, etc. You can also define the operation to be one of many different things, such as multiplication, vector addition, function composition, matrix multiplication, etc. I chose the set and operation as I did because they are easy to work with. Now that we have a set and an operation I’ll move to the way it has to act, or the properties.
The first property that I am going to discuss is the inclusion of the identity element. The identity element is the element that returns the element it is combined with under the operation. In the case of G the identity element is 0. This is because we’re using the addition operation and 0 + any element = any element, for example 0 + 1 = 1. I know this isn’t a very complicated issue for this group; however this property is a lot more complicated to verify when dealing with other operations, such as composition of functions.
Next I’m going to talk about the inverse elements. Every element of G has to have another element of G that when combined using the defined operation returns the identity element. This is where we use modulo arithmetic. For example 1 + 4 = 5, however 5 mod 5 = 0, therefore 4 and 1 are inverses of each other, the same is true for 2 and 3. 0 is its own inverse because 0 + 0 = 0. Again this is not very complicated to check because of the simplicity of the set and operation.
The associative property is next. If we take three arbitrary elements of the group, I’ll just choose 1, 2, and 3. Then we combine these elements with the operation 1 + 2 + 3, and then they have to have the same result no matter how the operations are ordered. To illustrated this property looks like this
( 1 + 2 ) + 3 = 1 + ( 2 + 3 ). No matter which elements you add together first the result has to be the same. Addition is always associative so this is a trivial point.
The last property to discuss is closure under the operation. This property states that whenever two elements of a group are combined using the operation the result has to be another element of the group. This is also where modulo arithmetic is important. An example is 4 + 3 = 7, 7 mod 5 = 2, so the result of this operation is another group element. Every element combined with any other element has to have a result that is an element of the group.
Seeing how long this article has become just going over the basics I will put off going over more information unless there is more interest. The easiest way to relate this to cryptology is to talk about permutation groups and inverses. When you encrypt a message in a simple way you are basically permuting the information. Then if you talk about a permutation group, the inverse elements are what allow you to get the original information out of the encrypted information. Basic mission 6 is a good example of finding an inverse, you figure out what has to be done to get the original information, so the algorithm you use to get the password is the inverse of the algorithm used to encrypt the password.
I realize that this article seems really simplistic, but simplicity in the beginning is a good way to build up to complexity later. This article barely even scratches the surface of group theory, and an abstract algebra class will spend a quarter of a semester approximately on how to prove sets are groups. If there are any questions about the material I presented please feel free to ask for clarification. There are other properties that apply to groups also that I didn’t go into here that classify a group into different categories.
If there is a desire for more let me know and I will be happy to write more articles