Linear time algorithms for Abelian group isomorphism and related problems

摘要

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(nlogn) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(nlogn) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1–9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian.