Integer factoring and modular square roots

DOI10.1016/j.jcss.2015.08.001zbMath1330.03088arXiv1207.5220OpenAlexW1804423330MaRDI QIDQ896029

Emil Jeřábek

Publication date: 11 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.5220

zbMATH Keywords

bounded arithmeticquadratic residuesearch probleminteger factoringPPA

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) First-order arithmetic and fragments (03F30) Factorization (11Y05)

Related Items

TFNP: An Update ⋮ The Journey from NP to TFNP Hardness ⋮ Approximate counting and NP search problems ⋮ Unique end of potential line ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Reductions in \textbf{PPP} ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Towards a unified complexity theory of total functions ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ 2-D Tucker is PPA complete ⋮ Unnamed Item ⋮ Unique End of Potential Line ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Unnamed Item
• Unnamed Item
• Propositional proofs and reductions between NP search problems
• Combinatorial principles in elementary number theory
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• PRIMES is in P
• The least quadratic non residue
• Explicit Bounds for Primality Testing and Related Problems
• Abelian groups and quadratic residues in weak arithmetic
• On Independence of Variants of the Weak Pigeonhole Principle

This page was built for publication: Integer factoring and modular square roots