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)?

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 5, 2016 at 13:41
  • 2
    $\begingroup$ see also NP complete variant of factoring / Theoretical Computer Science $\endgroup$
    – vzn
    Commented Feb 5, 2016 at 16:00

2 Answers 2


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$.

  • 1
    $\begingroup$ Thank you. And do I understand correctly that the AKS algorithm can tell us whether or not a number is prime in polynomial time, but if it is not prime it does not tell us the factors? $\endgroup$
    – Fequish
    Commented Feb 5, 2016 at 14:51
  • 1
    $\begingroup$ @Fequish : ​ If it is not prime then AKS does not tell us the factors. ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Feb 5, 2016 at 15:38
  • 2
    $\begingroup$ 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). $\endgroup$ Commented Feb 5, 2016 at 15:42
  • $\begingroup$ Yuval, wouldn't Pollard-Rho be a bit faster? (it should find the smallest factor of a composite number in O (n^(1/4)), except if n is prime then you have to give up at some point and switch to proving that n is prime). $\endgroup$
    – gnasher729
    Commented Oct 31, 2022 at 9:23
  • $\begingroup$ Pollard's rho algorithm is probabilistic, and its (heuristic) expected running time is a lot slower than more modern algorithms, unless there is a small prime factor. $\endgroup$ Commented Oct 31, 2022 at 21:49

To add to Yuval's answer: AKS primality testing was discovered in 2002. Prior to that we didn't have a polynomial time algorithm to check if a number is prime. However Pratt discovered in 1975 what is now known as Pratt certificates for primality and proved that Primes is in NP. We can include these Pratt certificates of primality for the factors in our certificate to show that FACTOR is in coNP in place of using the AKS algorithm to check if factors are prime directly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.