AnO(n) Algorithm for Abelianp-Group Isomorphism and anO(n log n) Algorithm for Abelian Group Isomorphism

摘要

The isomorphism problem for groups is to determine whether two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. Tarjan has shown that this problem can be done in timeO(nlog n+O(1)) for groups of cardinalityn. Savage has claimed an algorithm for showing that if the groups are Abelian, isomorphism can be determined in timeO(n2). We improve this bound and give anO(n log n) algorithm for Abelian group isomorphism. Further, we show that if the groups are Abelianp-groups then isomorphism can be determined in timeO(n). We also show that the elementary divisor sequence for an Abelian group can be determined in timeO(n log n) and for an Abelianp-group it can be determined in timeO(n).