FAC ∈ coNP

Inclusion · Pra75

Statement

The decision version of factoring is in coNP: a witness that $N$ has no nontrivial divisor at most $k$ is the complete prime factorization of $N$ together with a succinct primality certificate for each prime factor, showing that $N$ is prime or that every prime factor exceeds $k$ — Pra75. Hence factoring is in $\mathbf{NP}\cap \mathbf{coNP}$ and is not $\mathbf{NP}$-hard under Cook reductions unless $\mathbf{NP}=\mathbf{coNP}$ — standard.

Sketch

A Pratt certificate for a prime $p$ is a generator $g$ of ${\mathbb{Z}}_p^{\ast }$ together with the prime factorization of $p-1$ and, recursively, certificates for its prime factors; the verifier checks $g^{p-1}\equiv 1$ and $g^{(p-1)/r}\not\equiv 1(\mathrm{mod}p)$ for each prime $r\mid p-1$. The certificate has $O({\log }^{2}p)$ bits — Pra75.

Notes

• Primality is in fact decidable in deterministic polynomial time, which makes the certificates unnecessary for membership in $\mathbf{coNP}$ — AKS04.
• Factoring is also in TFNP, in BQP — Shor97 — and, under randomized reductions, in PPA and PWPP — Jer16.