Group Theory
The goal of the next few weeks will be to see a famous encryption scheme called ElGamal; to see and understand this we will need to do a little preliminary work. Next week, we will look at what we call ‘hard problems’ in cryptography. This week, we will introduce group theory.
What is group theory?
The concept of group theory is central to the area of abstract algebra and has wide ranging uses — from particle physics to classifying crystal structures in chemistry. Groups are also prominent in cryptography. For the ElGamal encryption scheme, we will need to use Cyclic groups: you will see the definition of these at the end of today’s tutorial.
The key conceptual difference between a group and algebraic structures, which you may have seen before, is that there is only one operator. That is, we only consider multiplication (said to be a group with respect to the multiplication operator) or addition (said to be a group with respect to the addition operator).
How do you define a group?
A group is a set, G, together with an operator, •, which is called the group law of G. This allows one to combine elements of the group together, denoted a•b, or ab. A group (G, •) must satisfy the following properties:
- Closure: For all a, b in G, a•b must also be in G;
- Associativity: For all a, b and c in G, we must have (a•b)•c =a•(b•c);
- Identity: There must exist an element e, such that for all a in G we have a•e = e•a = a;
- Inverse: For every a in G there must exist an element b, such that a•b = b•a = e, where e is the identity element.
Exercise: is it a group?
Think about the set of integers, that is the numbers with respect addition:
…, -3, -2, -1, 0, 1, 2, 3, …
Do they form a group? Try to write your reasoning down in a structured way.
Hint: If it is a group, you need to show it meets the properties in the definition above.
As the concept of a group can be a little tricky let us look at a couple of examples ourselves.
Examples: do you have reasoning and proof?
Determine whether or not the following are groups. Either provide a proof they are a group or a reason they are not:
- The natural numbers (0,1,2,…) with the addition operator a group.
This set does not form a group. How do we find an inverse? Take a that is non-zero in the set, there does not exist b such that a + b = 0.
- The set {0,1,2,…,n-1} with the addition operation taken modulo n.
This is a group, often called the cyclic group of order n.
- Closure: We are working working mod n, the property of closure comes from this;
- Associativity: this comes from the associativity of addition;
- 0 is the identity as the operation is addition;
- 0 is the inverse of 0 and n — a is the inverse of a when a is non zero.
Before we move onto look at cyclic groups, there are two pieces of terminology we need to consider: the order of a group and the order of an element.
Definition: the order of a group
We say the order of a group is the cardinality (size) of the set of it’s elements.
Definition: the order of an element of a group
The order of an element, a, of a group is the smallest integer, m, such that am = e, where e is the identity element. If there does not exist such an m, then we say the element has infinite order.
What is a cyclic group?
We have just seen the definition of a group. Now, we will look at the concept of a cyclic group.
Definition: cyclic group
A cyclic group is a group that is generated by one element. That is, every element of the group can be formed by performing the group operation on the generator.
G = ＜g＞ = {gn | n is an integer}
Here, ＜g＞, is the notation representing the cyclic group generated by g.
Further reading:
- Look up some other examples of cyclic groups and check they meet the definitions of a group we have given in this tutorial.
This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.
If you enjoyed this article, you might consider coming to our course in Cambridge this summer on the Mathematics behind Cryptography.
