# Small generating set-finding problem for black-box groups

## Description

We are given a group $G$ of order $N$ is specified by means of an encoding. We need to find a generating set for $G$ of size at most $\log_2N$.

A somewhat stronger requirement (which will guarantee this one) is: we need to find a generating set in which no element is redundant (that is, throwing out any element makes the subset non-generating).

## Algorithms

### Deterministic algorithms

Black-box group algorithm for small generating set-finding problem Takes time $O(N\log_2^2N)$ times the time for group operations. This is polynomial time in the order of the group. Does not necessarily find a generating set of minimum size, but (in one version) it finds a minimal generating set (i.e., a generating set in which no element is redundant). If the max-length is $\ell$, takes time $O(N\ell^2)$ times the time for group operations.
Black-box group algorithm for minimum size generating set-finding problem Takes time $O(N^{\log_2N + 1}\log_2N)$ times the time for group operations. This is not polynomial time but is quasipolynomial time in the order of the group. Finds a generating set of minimum size. If the minimum size of generating set is $s$, takes time $O(N^{s+1}s)$ times the time for group operations.
Conversion of black-box group algorithm dependent on generating set to black-box group algorithm For the black-box group version, we obtain that if there is a polynomial-time algorithm (polynomial in the order of the group) for carrying out a particular task given a generating set, then there is also a polynomial-time algorithm in general. Black-box group algorithm for small generating set-finding problem, which is $O(N\log_2^2N)$ where $N$ is the order of the group. generating set-based black-box group algorithm for abelianness testing takes time $O(N\log_2^2N)$ and is thus faster than brute-force black-box group algorithm for abelianness testing, which takes time $O(N^2)$.