  We show that there is a dense set $\ourset\subseteq \mathbb{N}$ of group
orders and a constant $c$ such that for every $n\in \ourset$ we can decide in
time $O(n^2(\log n)^c)$ whether two $n\times 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\times 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.
