I recommend the Handbook of Computation Group Theory, especially chapter 2 (omitting 2.4.4 and 2.5) and chapter 8.1 and 8.7.
Outline
Constructing groups of order $n$ is inductive: we assume that one has constructed all groups whose order properly divides $n$ and have them sorted nicely.
To construct the group $G$ we try a few things:
- If $G$ is solvable and $G/\Phi(G)$ is already constructed, use the Frattini extension method to construct $G$
- If $G$ is solvable and $\Phi(G) = 1$, then Gaschütz showed $G = M \ltimes \operatorname{Fit(G)}$ and $\operatorname{Fit}(G)$ is a (direct product of) elementary abelian group(s) on which $G$ acts semi-simply, so $M$ is on the list kindly computed for us by M.W. Short.
Hence if $G$ is solvable, then either we use cohomology to find $G$ from $G/\Phi(G)$, or we use ordinary character theory of $M$ (already constructed) to find $G$ when $\Phi(G)=1$.
If $G$ is not solvable, then the paper mostly cheats because the possibilities for not-solvable groups of this order are quite limited.
- If $G$ is not solvable, but $G' < G$, then $G$ has a maximal normal subgroup $M$ of index a prime $p$. We've already constructed $M$, so we use the theory of cyclic extensions (the upward extension method) to find $G$ from $M$ and $C_p$
- If $G$ is not solvable, and $G' = G$, then $G$ is on the list of perfect groups which Derek Holt and Wilhelm Plesken kindly computed for us.
Extensions
Extension theory is only used in the first bullet point of each case. The second bullet point uses table lookup, because someone else has already done the work here (and written a book about their techniques).
The two types of extensions are completely different, and best learned separately.
The first type is (non-split) extension by a minimal normal abelian subgroup. Since the quotient group is polycyclic (finite solvable in fact), we use the techniques of 8.7.2 (tails) to turn this into a linear algebra nullspace calculation. If you understand collection and/or polycyclic generating sequences, this stuff is pretty clear. It boils down to “multiplication is associative, so when I define what g*h equals, I need to make sure it is still associative.” The marvelous thing is that in this case the rules for associativity are linear. In particular, you don't particularly need to know what second cohomology “is” if you understand collection and tails.
The second type is (upwards) cyclic extension. This is in principle easy, but is a little bit of a hassle since it requires fairly detailed calculations in automorphism groups.
Difficulties
There are two main times one has difficulties: construction and isomorphism rejection.
Computation time during construction is usually not a problem, but things get bad when $H^2(G/M,M)$ is large as we need to find orbits on a large vector space. For example if $G/M$ is very nearly (or is) a $p$-group, then the cohomology quickly gets out of control. For this reason, $p$-groups are handled using O'Brien's $p$-group generation algorithm, and $p^nq$ groups are handled using the “split extension” method.
Isomorphism rejection is very hard if the same group is constructed many, many times. During construction, groups with the same recipe that are isomorphic are automatically rejected. However, different recipes can give the same group. It is important to minimize this, but in the range Besche–Eick was working in, the Frattini subgroup was enough: all recipes had to specify $G/\Phi(G)$, but one could specify $\Phi(G)$ in many (many) different ways. Since ingredients for $\Phi(G)$ are reasonably rare for the allowed $G/\Phi(G)$, this worked out. For $G/\Phi(G)$ a $p$-group, things go very badly, so that is why the other algorithms had to be used.
