Polynomial-time isomorphism testing of groups of most finite orders
Preprint
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$.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Isomorphism testing of groups of cube-free orderJournal of Algebra, 2020
- Rigorous analysis of a randomised number field sieveJournal of Number Theory, 2018
- An introduction to univalent foundations for mathematiciansBulletin of the American Mathematical Society, 2018
- A fast isomorphism test for groups whose Lie algebra has genus 2Journal of Algebra, 2017
- Practical graph isomorphism, IIJournal of Symbolic Computation, 2014
- The seven virtues of simple type theoryJournal of Applied Logic, 2008
- Linear time algorithms for Abelian group isomorphism and related problemsJournal of Computer and System Sciences, 2007
- The Pohlig–Hellman Method Generalized for Group Structure ComputationJournal of Symbolic Computation, 1999
- Sylow Subgroups in ParallelJournal of Algorithms, 1999
- Computing in general abelian groups is hardTheoretical Computer Science, 1985