Integer factoring and modular square roots

0451577 - MÚ 2016 RIV US eng J - Journal Article
Jeřábek, Emil
Integer factoring and modular square roots.
Journal of Computer and System Sciences. Roč. 82, č. 2 (2016), s. 380-394. ISSN 0022-0000. E-ISSN 1090-2724
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : integer factoring * quadratic residue * PPA
Subject RIV: BA - General Mathematics
Impact factor: 1.678, year: 2016
http://www.sciencedirect.com/science/article/pii/S0022000015000768

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.
Permanent Link: http://hdl.handle.net/11104/0252707