FAC ⊆ TFNP

Inclusion · folklore

Statement

The search problem underlying FAC — given an integer $N\ge 2$, output its prime factorization — is in TFNP — folklore.

Sketch

Totality is the fundamental theorem of arithmetic; the verifier checks ${\prod }_i{p}_i^{e_i}=N$ and tests each $p_i$ for primality in polynomial time.

Notes

• Factoring reduces in randomized polynomial time to a problem in PPA and to WeakPigeon in PPP; under the generalized Riemann hypothesis both reductions are deterministic — Jer16.