Black-box group algorithm for group isomorphism problem

Summary

Item	Value
Problem being solved	group isomorphism problem for black-box groups
Input format	finite groups $G_{1},G_{2}$ given by means of encodings
Output format	No if they are not isomorphic Yes if they are isomorphic In the Yes case, it is also possible to additionally output the isomorphism as an explicit bijection between generating sets, or even as an explicit bijection between the groups.
Running time	If the orders of the groups equal $N$ and the minimum size of generating set is $s$, then $O(N^{s+1}s)$ times the time taken for group operations. In the worst case, this becomes $O(N^{\log _{2}N+1}\log _{2}N)$ times the time taken for group operations.

Idea and outline

The approach is as follows. Note that each step takes $O(N^{s+1}s)$ (multiplied by the time taken for group operations) time, hence the total is also $O(N^{s+1}s)$:

1. Use the black-box group algorithm for generating set-finding problem to find a generating set of minimum size for $G_{1}$.
2. Try every possible subset of $G_{2}$ of the same size and every possible bijection from the generating set of $G_{1}$ to that. The number of possibilities is $O(N^{s})$. Use the black-box group algorithm for checking whether a bijection between generating sets extends to a group isomorphism to determine whether that bijection extends to a group isomorphism. This takes time $O(Ns)$ times the time taken for group operations.