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 algorithm that determines if two Abelian groups with n elements each are isomorphic. The running time of this algorithm is O(n log p), where p is the smallest prime not dividing n. When n is odd, this algorithm runs in linear time; in general, it takes time at most O(n log log n), improving upon an algorithm with O(n log n) running time due to Vikas. Our Abelian group isomorphism algorithm is a byproduct of an algorithm that computes the orders of all elements in any group (not necessarily Abelian) of size n in time O(n log p), where p is the smallest prime not dividing n. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian.
展开▼
