Polynomial-time isomorphism testing of groups of most finite orders

Abstract

[PLEASE SEE COMMENT] We consider the isomorphism problem for finite abelian groups and finite meta-cyclic groups. We prove that for a dense set of positive integers $n$, isomorphism testing for abelian groups of black-box type of order $n$ can be done in time polynomial in $\log n$. We also prove that for a dense set of orders $n$ with given prime factors, one can test isomorphism for coprime meta-cyclic groups of black-box type of order $n$ in time polynomial in $\log n$. Prior methods for these two classes of groups have running times exponential in $\log n$.

This draft contains some erroneous statements and some proofs have gaps; please refer to the following publications for corrections. (1) Isomorphism testing of groups of cube-free order. J. Algebra 545 (2020) 174-197. (2) Group isomorphism is nearly-linear time for most orders. FOCS 2021 (accepted, arXiv:2011.03133) (3) The content on groups of black-box type will be revised in a different draft

References in corpus (3)

• The threshold for subgroup profiles to agree is $\Omega (\log n)$
• Rigorous Analysis of a Randomised Number Field Sieve
• Isomorphism testing of groups of cube-free order

Cited by in corpus (2)

• Isomorphism testing of groups of cube-free order
• A Frobenius-Schreier-Sims Algorithm to tensor decompose algebras