Integer factoring and modular square roots

DOI10.1016/J.JCSS.2015.08.001zbMATH Open1330.03088arXiv1207.5220OpenAlexW1804423330MaRDI QIDQ896029FDOQ896029

Authors: Emil Jeřábek 

Publication date: 11 December 2015

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

Abstract: Buresh-Oppenheim proved that the NP search problem to find nontrivial factors of integers of a special form belongs to Papadimitriou's class PPA, and is probabilistically reducible to a problem in PPP. In this paper, we use ideas from bounded arithmetic to extend these results to arbitrary integers. We show that general integer factoring is reducible in randomized polynomial time to a PPA problem and to the problem WEAKPIGEON in PPP. Both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. We also show (unconditionally) that PPA contains some related problems, such as square root computation modulo n, and finding quadratic nonresidues modulo n.

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

Recommendations

• Integer factoring and compositeness witnesses
• Reductions among number theoretic problems
• scientific article; zbMATH DE number 3954815
• scientific article; zbMATH DE number 167875
• Reductions in \textbf{PPP}

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)

Cites Work

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

Cited In (15)

• Towards a unified complexity theory of total functions
• Title not available (Why is that?)
• Reductions in \textbf{PPP}
• 2-D Tucker is PPA complete
• Approximate counting and NP search problems
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Unique End of Potential Line
• The journey from NP to TFNP hardness
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Unique end of potential line
• Towards a Unified Complexity Theory of Total Functions
• TFNP: an update
• Note on constrained long choice with multiple beginning elements
• The classes PPA-\(k\): existence from arguments modulo \(k\)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896029)