Group isomorphism is nearly-linear time for most orders

We show that there is a dense set Υ ⊆ N of group orders and a constant c such that for every n ∈ Υ we can decide in time O(n 2 (log n) c ) whether two n × n multiplication tables describe isomorphic groups of order n. This improves significantly over the general n O(log n) -time complexity and shows that group isomorphism can be tested efficiently for almost all group orders n. We also show that in time O(n 2 (log n) c ) it can be decided whether an n × n multiplication table describes a group; this improves over the known O(n 3 ) complexity. Our complexities are calculated for a deterministic multi-tape Turing machine model. We give the implications to a RAM model in the promise hierarchy as well.