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}^{2}N)\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.