FAC ∈ PPA (under randomized reductions)

Inclusion · Jer16

Statement

Factoring reduces in randomized polynomial time to a problem in PPA, so lies in PPA under randomized reductions, and in deterministic polynomial time under the generalized Riemann hypothesis — Jer16. Hardness of factoring therefore makes PPA hard on average under the corresponding reductions — folklore.

Notes

• The same paper reduces factoring to Weak Pigeon: FAC ∈ PWPP — Jer16.