ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM

DOI10.17223/20710410/33/8zbMath1490.68119OpenAlexW2550788273MaRDI QIDQ5150750

Alexander N. Rybalov

Publication date: 15 February 2021

Published in: Prikladnaya diskretnaya matematika (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/pdm556

zbMATH Keywords

discrete logarithm problemprobabilistic algorithmgeneric complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (2)

Generic amplification of recursively enumerable sets ⋮ ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES

Cites Work

• Average-case complexity and decision problems in group theory.
• Generic complexity of Presburger arithmetic
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• Generic complexity of undecidable problems
• Unnamed Item
• Unnamed Item

This page was built for publication: ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM