# Why is FACTOR in Co-NP?

I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS primality test, and I believe this works for COMPOSITE as well.

As for FACTOR,

$$FACTOR = \{(m,r) :\;\; \exists s \text{ such that} 1<s<r \text{ and } s \text{ divides } m\}$$

from what I have read it seems that it is in $NP \cap Co-NP$. I see that it is in $NP$ since a certificate would consist of a prime divisor of $m$ less than $r$. But what kind of certificate can establish that there is no such prime divisor (in polynomial time)?

• For a language to be in NP proof that input belongs to the language has to have a certificate which can be verified in polynomial time. It does not mean that a certificate for inputs not belonging to the language exists which can be verified efficiently. Commented Feb 5, 2016 at 13:41
• – vzn
Commented Feb 5, 2016 at 16:00

A certificate for there being no non-trivial divisor of $m$ smaller than $r$ is the factorization of $m$. We can check in polynomial time that all factors are indeed prime (since primality is in P by AKS primality test), that their product is $m$, and that all of them are at least $r$.
• Factoring isn't known to be doable in polynomial time. The best publicly known algorithm has heuristic complexity $e^{O((\log n)^{1/3}(\log\log n)^{2/3})}$ (here $n$ is the number itself). Commented Feb 5, 2016 at 15:42