Polynomial time tests for surjective maps between certain finite groups
Algorithms for Finite Group Epimorphism Testing
Data Structures and AlgorithmsComputational Complexity
Summary
The problem studied is how to decide if you can map one finite group onto another in a way that covers every element of the second group (called a surjective homomorphism). The authors look at groups with special internal structure and develop algorithms that decide this question quickly, in time that grows reasonably with the size of the groups. These results build on previous work that could quickly test if two such groups were basically the same (isomorphic). Their methods work for several important types of groups that mathematicians often study.
What this means in practice
- •For software engineers working on computational algebra: Improve group-theoretic algorithms by efficiently testing surjective mappings between structured finite groups.
- •For cryptography developers: Use fast epimorphism tests in designing or analyzing cryptographic protocols relying on group structure mappings.
Authors
Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
Abstract
The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.