In bounded arithmetic, we study weak first-order theories with close connections to complexity: there is a loose three-way correspondence between theories of arithmetic, computational complexity classes, and propositional proof systems. When a theory T corresponds to a complexity class C, this usually means that problems from C have provably total definitions in T by formulas of low complexity such that T can prove their basic properties, and on the other hand, existential consequences of T of certain complexity can be witnessed by C-functions ("witnessing theorem").

Typical applications of witnessing theorems are to show that certain statements are unprovable in T, using (or just assuming) that the corresponding witnessing functions are not computable in C. But as an interesting twist, we occasionally get to use them in the other direction: we prove the existence of an algorithm of certain complexity that solves a particular task by proving something in bounded arithmetic and applying a witnessing theorem.

In this talk, I will present an example of the latter phenomenon. It concerns one of the most fundamental computational problems: integer factoring (considered as a search problem--given a composite integer, find one of its proper divisors), as well as some related number-theoretic problems.

In prior work, Buresh-Oppenheim proved that factoring of integers of a certain special form belongs to Papadimitriou's class PPA of search problems solvable by a "parity argument". We will show that general integer factoring has a randomized reduction to PPA (that may be derandomized assuming a GRH/ERH), and PPA contains outright the problems of computing square roots modulo arbitrary integers, and finding quadratic nonresidues. The main ingredient in the algorithms is extracted by applying a witnessing theorem to a certain consequence of the quadratic reciprocity theorem, which we prove in an arithmetical theory corresponding to PPA.