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

From Groupprops

## 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 with an encoding, a subgroup of specified by a membership test Assume it is possible to enumerate all elements of |

Output format | Yes/No depending on whether is normal in Optionally, if the subgroup is not normal, elements such that . |

Running time | (Time taken for enumeration of all group elements)+ (Time taken to do membership test on all group elements) + ( (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 . Note that for , we can enumerate all elements by first enumerating all elements of and then filtering the set using the membership test for .

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.