Computing in general Abelian groups is hard

DOI10.1016/0304-3975(85)90061-1zbMath0585.68053OpenAlexW2015970419MaRDI QIDQ1070820

Costas S. Iliopoulos

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90061-1

zbMATH Keywords

generatorscyclicitycanonical structureprime factorizationprimality testingorder of an elementrelative complexitygroup-theoretic complexitymembership testingPolynomial time reductionsset of defining relations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Generators, relations, and presentations of groups (20F05) Finite abelian groups (20K01) Software, source code, etc. for problems pertaining to number theory (11-04) Primes (11A41)

Related Items

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ Generation of finite groups with cyclic Sylow subgroups ⋮ Algorithms for computing parameters of graph-based extensions of BCH codes ⋮ Analysis of algorithms on problems in general abelian groups ⋮ Computing a basis for a finite Abelian p-group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On distinguishing prime numbers from composite numbers
• Analysis of algorithms on problems in general abelian groups
• Group-theoretic algorithms and graph isomorphism
• Riemann's hypothesis and tests for primality
• On the computational power of pushdown automata
• Fast multiplication of large numbers
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
• The distribution of quadratic residues and non‐residues
• Factorization and Primality Tests