# Membership test-based black-box group algorithm for normality testing

## Summary

Item Value
Problem being solved normality testing problem: test whether a given subgroup of a given group is normal
Input format A finite group $G$ with an encoding, a subgroup $H$ of $G$ specified by a membership test
Assume it is possible to enumerate all elements of $G$
Output format Yes/No depending on whether $H$ is normal in $G$
Optionally, if the subgroup is not normal, elements $g \in G, h \in H$ such that $ghg^{-1} \notin H$.
Running time (Time taken for enumeration of all group elements)+ (Time taken to do membership test on all group elements) + ($O(N \log_2^2N) \times$ (Time for group operations))

## Idea and outline

The idea is to first use the black-box group algorithm for small generating set-finding problem to separately compute small generating sets for $G,H$. Note that for $H$, we can enumerate all elements by first enumerating all elements of $G$ and then filtering the set using the membership test for $H$.

Once we have small generating sets for both, we can use the generating set-cum-membership test-based black-box group algorithm for normality testing. Note that the actual normality testing takes negligible time compared to the time spent computing the generating sets.