FAC ∈ NP

Inclusion · folklore

Statement

The decision version of factoring, $\{(N,k):N\text{ has a nontrivial divisor }d\le k\}$, is in NP: such a divisor is a witness checked by one division — folklore. A search algorithm for factors follows from a decision algorithm by binary search on $k$ — folklore.

Notes

• The complement is in $\mathbf{NP}$ as well: FAC ∈ coNP — Pra75.