Groups

A group is a set with a binary operation, which takes two elements of the group as input and outputs an element of the group. This operation is closed and associative. There is an identity element. Every element has an inverse element. That's it, that's all there is to it.

Less abstractly, a group can be thought of as a way of describing the set of ways that an object can be symmetric, and the relations those symmetry transformations have with each other. The structure of the group, in terms of the number of elements and their relations (which elements multiply together to make which other elements), is what distinguishes different groups. When two groups have the same structure, they are said to be isomorphic, and are generally considered the same group in an abstract sense, even if they are implemented in different ways. For example, the group of symmetries of a triangle is the same as the group of permutations of three points, and we just call them the same group, namely $S_3$.

Note that the group theory terms "isomorphic" and "isomorphism" have nothing to do with the same cryptography terms which are also of fundamental importance to this wiki. Hopefully that's not too confusing.

There are only finitely many groups of any given (finite) size. Counting the number of possible distinct groups for a given size is incredibly difficult.

There are a few families of groups that we commonly work with, which have their own special notation for their names:

• Cyclic groups, $C_n$, $n$ elements representing the rotational symmetries of an $n$-gon
• Dihedral groups $D_{2n}$, $2n$ elements representing the rotational and reflectional symmetries of an $n$-gon
• Alternating groups $A_n$, $n!/2$ elements consisting of all even permutations of $n$ objects
• Symmetric groups $S_n$, $n!$ elements consisting of all permutations of $n$ objects

Some families of groups come from linear algebra:

• General linear groups $GL(m, n)$ consisting of all $m$-dimensional linear transformations (invertible $m \times m$ matrices) over a field with $n$ elements
• Special linear groups $SL(m, n)$, same as above but with matrices of determinant 1
• Affine general linear groups $AGL(m, n)$
• Projective special linear groups $PSL(m, n)$

There are many other families of groups not worth listing here, and weird exceptions like sporadic groups... Classification of groups is a very complicated problem. There's also special notation for a few unusual groups like the quaternion group $Q_8$ as well as some others.

Groups can be built up from smaller groups by extensions, such as using a direct product of two groups, or a semidirect product of two groups, as well as some more obscure extension methods that are usually not very relevant compared to taking products.

It's important to notice that commutativity was not one of the properties listed in the definition of a group. Groups can be broadly divided into commutative and non-commutative groups. The structure of commutative groups is much simpler, and can be summarized as: Every finite commutative group is a direct product of some number of cyclic groups, this is known as the fundamental theorem of finite abelian groups. The structure of non-commutative groups is where things get extremely complicated.

The smallest unit of groups necessary for building up all groups are the "simple" groups, which are really not simple at all, and are defined as groups with no normal subgroups. The full classification of finite simple groups is known, and was one of the largest and most complicated proofs ever made. Obviously I will not get into any of the details of that here.

Groups are relevant to cryptography for a number of reasons, well beyond what is in this wiki, but for our purposes, groups are interesting because using a group as the internal state structure for a cipher seems to be one of the main conditions necessary for the cipher to produce isomorphs.

Other important information about group theory that comes up in this wiki a lot are subgroups and cosets. Not sure whether I'll try to explain those or leave it to Wikipedia.

For more information:

See the Wikipedia article for an overview on groups.

Also check out the Groupprops wiki for some information on specific groups and classes of groups, along with some proofs about groups.