Integer factoring and modular square roots

DOI10.1016/J.JCSS.2015.08.001MaRDI QIDQ896029zbMATH OpenOpenAlexFDO

Authors 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)

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.

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}

Cites work

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

Cited in

(15)

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

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)