ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM

DOI10.17223/20710410/28/6OpenAlexW4249769092MaRDI QIDQ5150686

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/pdm509

zbMATH Keywords

probabilistic algorithmquadratic residuegeneric complexity

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Related Items

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

Cites Work

• Unnamed Item
• 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
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Generic complexity of undecidable problems