Integer factoring and modular square roots (Q896029)

In the paper under review, it is shown that general integer factoring is reducible in randomized polynomial time to a PPA problem and to the problem WEAKPIGEON \(\in\) PPP. It is claimed that both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. It is also proved that PPA contains some related problems such as square root computation modulo \(n\) and finding quadratic nonresidues modulo \(n\). In the proofs, some ideas from bounded arithmetic are used. The results of the paper extend the results of \textit{J. Buresh-Oppenheim} [``On the TFNP complexity of factoring'', (unpublished note), \url{http://www.cs.toronto.edu/~bureshop/factor.pdf}] to arbitrary integers.