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 arithmeticinteger factoringPPAquadratic residuesearch problem

Mathematics Subject Classification ID

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

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

• Abelian groups and quadratic residues in weak arithmetic
• Combinatorial principles in elementary number theory
• Explicit Bounds for Primality Testing and Related Problems
• scientific article; zbMATH DE number 1215494 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• 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

(21)

• Reductions in \textbf{PPP}
• Towards a unified complexity theory of total functions
• 2-D Tucker is PPA complete
• Unique end of potential line
• The journey from NP to TFNP hardness
• Towards a Unified Complexity Theory of Total Functions
• Approximate counting and NP search problems
• Unique End of Potential Line
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• TFNP: an update
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Note on constrained long choice with multiple beginning elements
• Total NP search problems with abundant solutions
• TFNP intersections through the Lens of feasible disjunction
• One-way functions vs. TFNP: Simpler and improved
• On the complexity of some restricted variants of \textsc{Quotient Pigeon} and a weak variant of \textsc{Kőnig}
• Prime factorization in models of \(\mathrm{PV}_1\)
• The \(\mathtt{PPP}\)-completeness of Ward-Szabó

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)