Finite abelian group isomorphism test reaches near optimal speed
Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
Data Structures and Algorithms
Summary
The paper studies how quickly we can check if two finite abelian groups are essentially the same, and how hard it is to find a basic building block (basis) for these groups. The authors provide a fast method for deciding isomorphism that is close to the best possible speed. They also show that finding a basis is fundamentally harder, needing more steps. This establishes clear differences in difficulty between these two problems within the same kind of mathematical groups.
What this means in practice
- •For cryptography engineers: Design cryptographic protocols that rely on understanding complexity of group isomorphisms using nearly optimal decision methods.
- •For computer algebra system developers: Implement more efficient group isomorphism testing in software that manipulates algebraic structures leveraging near-optimal complexity algorithms.
A theory result. No direct application yet.
Authors
Nader H. Bshouty
Abstract
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/4})$ group additions and runs in $\tilde O(n^{1/4})$ time. This improves the $\tilde O(\sqrt n)$ upper bound of Chen and Fu and matches Bshouty $Ω(n^{1/4})$ lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least $2/3$ requires $Ω(\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Θ(n^{1/4})$ and $\tildeΘ(\sqrt n)$, respectivel