Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups

We study isomorphism decision and basis construction for finite Abelian groups of known order $n$. We measure complexity by the number of additions performed in the groups and by the total running time. We give a randomized isomorphism decision algorithm that performs $\tilde{O}(n^{1\mathrm{/}4})$ group additions and runs in $\tilde{O}(n^{1\mathrm{/}4})$ time. This improves the $\tilde{O}(\sqrt{n})$ upper bound of Chen and Fu and matches Bshouty $\mathrm{\Omega }(n^{1\mathrm{/}4})$ lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least $2\mathrm{/}3$ requires $\mathrm{\Omega }(\sqrt{n})$ group additions in the worst case. This matches the $\tilde{O}(\sqrt{n})$ upper bound of Chen and Fu up to polylogarithmic factors. These results separate isomorphism decision from basis construction in finite Abelian groups: their optimal worst-case complexities are $\tilde{\mathrm{\Theta }}(n^{1\mathrm{/}4})$ and $\tilde{\mathrm{\Theta }}(\sqrt{n})$, respectivel